Cell walls of brown algae are complex supramolecular assemblies containing various original, sulfated, and carboxylated polysaccharides. Among these, the major marine polysaccharide component, alginate, represents an important biomass that is successfully turned over by the heterotrophic marine bacteria. In the marine flavobacterium Zobellia galactanivorans, the catabolism and uptake of alginate are encoded by operon structures that resemble the typical Bacteroidetes polysaccharide utilization locus. The genome of Z. galactanivorans contains seven putative alginate lyase genes, five of which are localized within two clusters comprising additional carbohydrate-related genes. This study reports on the detailed biochemical and structural characterization of two of these. We demonstrate here that AlyA1PL7 is an endolytic guluronate lyase, and AlyA5 cleaves unsaturated units, α-L-guluronate or β-D-manuronate residues, at the nonreducing end of oligo-alginates in an exolytic fashion. Despite a common jelly roll-fold, these striking differences of the mode of action are explained by a distinct active site topology, an open cleft in AlyA1(PL7), whereas AlyA5 displays a pocket topology due to the presence of additional loops partially obstructing the catalytic groove. Finally, in contrast to PL7 alginate lyases from terrestrial bacteria, both enzymes proceed according to a calcium-dependent mechanism suggesting an exquisite adaptation to their natural substrate in the context of brown algal cell walls.