Fucoidans from brown macroalgae are sulfated fucose-rich polysaccharides, that have several beneficial biological activities, including anti-inflammatory and anti-tumor effects. Controlled enzymatic depolymerization of the fucoidan backbone can help produce homogeneous, defined fucoidan products for structure-function research and pharmaceutical uses. However, only a few endo-fucoidanases have been described. This article reports the genome-based discovery, recombinant expression in Escherichia coli, stabilization, and functional characterization of a new bacterial endo-α-(1,4)-fucoidanase, Fhf1, from Formosa haliotis. Fhf1 catalyzes the cleavage of α-(1,4)-glycosidic linkages in fucoidans built of alternating α-(1,3)-/α-(1,4)-linked l-fucopyranosyl sulfated at C2. The native Fhf1 is 1120 amino acids long and belongs to glycoside hydrolase (GH) family 107. Deletion of the signal peptide and a 470 amino acid long C-terminal stretch led to the recombinant expression of a robust, minimized enzyme, Fhf1Δ470 (71 kDa). Fhf1Δ470 has optimal activity at pH 8, 37–40 °C, can tolerate up to 500 mM NaCl, and requires the presence of divalent cations, either Ca2+, Mn2+, Zn2+ or Ni2+, for maximal activity. This new enzyme has the potential to serve the need for controlled enzymatic fucoidan depolymerization to produce bioactive sulfated fucoidan oligomers.