Fucoidanase enzymes able to degrade fucoidan were produced by solid-state fermentation (SSF). The fermentation assays were initially carried out in a laboratory-scale rotating drum bioreactor, and two fungal strains (Aspergillus niger PSH and Mucor sp. 3P) and three algal substrates (untreated, autohydrolyzed, and microwave processed seaweed Fucus vesiculosus) were evaluated. Additionally, fermentations were carried out under rotational (10 rpm) and static conditions in order to determine the effect of the agitation on the enzyme production. Agitated experiments showed advantages in the induction of the enzyme when compared to the static ones. The conditions that promoted the maximum fucoidanase activity (3.82 U L−1) consisted in using Mucor sp. 3P as fungal strain, autohydrolyzed alga as substrate, and the rotational system. Such conditions were subsequently used in a 10 times larger scale rotating drum bioreactor. In this step, the effect of controlling the substrate moisture during the enzyme production by SSF was investigated. Moreover, assays combining the algal substrate with an inert support (synthetic fiber) were also carried out. Fermentation of the autohydrolyzed alga with the moisture content maintained at 80% during the fermentation with Mucor sp. 3P gave the highest enzyme activity (9.62 U L−1).