Choline and trimethylamine (TMA) are small molecules that play central roles in biological processes throughout all kingdoms of life. These ubiquitous metabolites are linked through a single biochemical transformation, the conversion of choline to TMA by anaerobic microorganisms. This metabolic activity, which contributes to methanogenesis and human disease, has been known for over a century but has eluded genetic and biochemical characterization. We have identified a gene cluster responsible for anaerobic choline degradation within the genome of a sulfate-reducing bacterium and verified its function using both a genetic knockout strategy and heterologous expression in Escherichia coli. Bioinformatics and electron paramagnetic resonance (EPR) spectroscopy revealed the involvement of a C–N bond cleaving glycyl radical enzyme in TMA production, which is unprecedented chemistry for this enzyme family. Our discovery provides the predictive capabilities needed to identify choline utilization clusters in numerous bacterial genomes, underscoring the importance and prevalence of this metabolic activity within the human microbiota and the environment.