Choline is ubiquitous in marine eukaryotes and appears to be widely distributed in surface marine waters; however, its metabolism by marine bacteria is poorly understood. Here, using comparative genomics and molecular genetic approaches, we reveal that the capacity for choline catabolism is widespread in marine heterotrophs of the marine Roseobacter clade (MRC). Using the model bacterium Ruegeria pomeroyi, we confirm that the betA, betB and betC genes, encoding choline dehydrogenase, betaine aldehyde dehydrogenase and choline sulfatase, respectively, are involved in choline metabolism. The betT gene, encoding an organic solute transporter, was essential for the rapid uptake of choline but not glycine betaine (GBT). Growth of choline and GBT as a sole carbon source resulted in the re-mineralization of these nitrogen-rich compounds into ammonium. Oxidation of the methyl groups from choline requires formyltetrahydrofolate synthetase encoded by fhs in R.pomeroyi, deletion of which resulted in incomplete degradation of GBT. We demonstrate that this was due to an imbalance in the supply of reducing equivalents required for choline catabolism, which can be alleviated by the addition of formate. Together, our results demonstrate that choline metabolism is ubiquitous in the MRC and reveal the role of Fhs in methyl group oxidation in R.pomeroyi.