Brown algae are important players in the global carbon cycle by fixing carbon dioxide into 1 Gt of biomass annually, yet the fate of fucoidan—their major cell wall polysaccharide—remains poorly understood. Microbial degradation of fucoidans is slower than that of other polysaccharides, suggesting that fucoidans are more recalcitrant and may sequester carbon in the ocean. This may be due to the complex, branched and highly sulfated structure of fucoidans, which also varies among species of brown algae. Here, we show that ‘Lentimonas’ sp. CC4, belonging to the Verrucomicrobia, acquired a remarkably complex machinery for the degradation of six different fucoidans. The strain accumulated 284 putative fucoidanases, including glycoside hydrolases, sulfatases and carbohydrate esterases, which are primarily located on a 0.89-megabase pair plasmid. Proteomics reveals that these enzymes assemble into substrate-specific pathways requiring about 100 enzymes per fucoidan from different species of brown algae. These enzymes depolymerize fucoidan into fucose, which is metabolized in a proteome-costly bacterial microcompartment that spatially constrains the metabolism of the toxic intermediate lactaldehyde. Marine metagenomes and microbial genomes show that Verrucomicrobia including ‘Lentimonas’ are abundant and highly specialized degraders of fucoidans and other complex polysaccharides. Overall, the complexity of the pathways underscores why fucoidans are probably recalcitrant and more slowly degraded, since only highly specialized organisms can effectively degrade them in the ocean.