Marine brown algae produce the highly recalcitrant polysaccharide fucoidan, contributing to long-term oceanic carbon storage and climate regulation. Fucoidan is degraded by specialized heterotrophic bacteria, which promote ecosystem function and global carbon turnover using largely uncharacterized mechanisms. Here, we isolate and study two Planctomycetota strains from the microbiome associated with the alga Fucus spiralis, which grow efficiently on chemically diverse fucoidans. One of the strains appears to internalize the polymer, while the other strain degrades it extracellularly. Multi-omic approaches show that fucoidan breakdown is mediated by the expression of divergent polysaccharide utilization loci, and endo-fucanases of family GH168 are strongly upregulated during fucoidan digestion. Enzymatic assays and structural biology studies reveal how GH168 endo-fucanases degrade various fucoidan cores from brown algae, assisted by auxiliary hydrolytic enzymes. Overall, our results provide insights into fucoidan processing mechanisms in macroalgal-associated bacteria.