The beneficial human gut bacterium Akkermansia muciniphila provides metabolites to other members of the gut microbiota by breaking down host mucin, but most of its other metabolic functions have not been investigated. A. muciniphila strain MucT is known to use cobamides, the vitamin B12 family of cofactors with structural diversity in the lower ligand. However, A. muciniphila MucT is unable to synthesize cobamides de novo, and the specific forms that can be used by A. muciniphila have not been examined. We found that the levels of growth of A. muciniphila MucT were nearly identical with each of seven cobamides tested, in contrast to nearly all bacteria that had been studied previously. Unexpectedly, this promiscuity is due to cobamide remodeling-the removal and replacement of the lower ligand-despite the absence of the canonical remodeling enzyme CbiZ in A. muciniphila We identified a novel enzyme, CbiR, that is capable of initiating the remodeling process by hydrolyzing the phosphoribosyl bond in the nucleotide loop of cobamides. CbiR does not share similarity with other cobamide remodeling enzymes or B12-binding domains and is instead a member of the apurinic/apyrimidinic (AP) endonuclease 2 enzyme superfamily. We speculate that CbiR enables bacteria to repurpose cobamides that they cannot otherwise use in order to grow under cobamide-requiring conditions; this function was confirmed by heterologous expression of cbiR in Escherichia coli Homologs of CbiR are found in over 200 microbial taxa across 22 phyla, suggesting that many bacteria may use CbiR to gain access to the diverse cobamides present in their environment.IMPORTANCE Cobamides, comprising the vitamin B12 family of cobalt-containing cofactors, are required for metabolism in all domains of life, including most bacteria. Cobamides have structural variability in the lower ligand, and selectivity for particular cobamides has been observed in most organisms studied to date. Here, we discovered that the beneficial human gut bacterium Akkermansia muciniphila can use a diverse range of cobamides due to its ability to change the cobamide structure via a process termed cobamide remodeling. We identify and characterize the novel enzyme CbiR that is necessary for initiating the cobamide remodeling process. The discovery of this enzyme has implications for understanding the ecological role of A. muciniphila in the gut and the functions of other bacteria that produce this enzyme.