Uptake of vitamin B12 is essential for many prokaryotes, but in most cases the membrane proteins involved are yet to be identified. We present the biochemical characterization and high-resolution crystal structure of BtuM, a predicted bacterial vitamin B12 uptake system. BtuM binds vitamin B12 in its base-off conformation, with a cysteine residue as axial ligand of the corrin cobalt ion. Spectroscopic analysis indicates that the unusual thiolate coordination allows for decyanation of vitamin B12. Chemical modification of the substrate is a property other characterized vitamin B12-transport proteins do not exhibit.