Humans harbor numerous species of colonic bacteria that digest the fiber polysaccharides in commonly consumed terrestrial plants. More recently in history, regional populations have consumed edible seaweeds (macroalgae) containing unique polysaccharides. However, it remains unclear how extensively gut bacteria have adapted to digest these novel nutrients. Here, we show that the ability of gut bacteria to digest seaweed polysaccharides is considerably more pervasive than previously appreciated. Using culture-based approaches, we show that known Bacteroides genes involved in seaweed degradation have mobilized into many members of this genus. We also identify new marine bacteria-derived genes, and their corresponding mobile DNA elements, that are involved in degrading several seaweed polysaccharides. Some of these new genes reside in gut-resident, Gram-positive Firmicutes, for which phylogenetic analysis suggests an origin in the Epulopiscium gut symbionts of marine fishes. Our results are important for understanding the metabolic plasticity of the human gut microbiome, the global exchange of genes in the context of dietary selective pressures and identifying new functions that can be introduced or engineered to design and fill orthogonal niches for a future generation of engineered probiotics.