Choline (N,N,N-trimethylethanolamine), which is widely distributed in membrane lipids and is a component of sediment biota, has been shown to be utilized anaerobically by mixed prokaryote cultures to produce methane but not by pure cultures of methanogens. Here, we show that five recently isolated Methanococcoides strains from a range of sediments (Aarhus Bay, Denmark; Severn Estuary mudflats at Portishead, United Kingdom; Darwin Mud Volcano, Gulf of Cadiz; Napoli mud volcano, eastern Mediterranean) can directly utilize choline for methanogenesis producing ethanolamine, which is not further metabolized. Di- and monomethylethanolamine are metabolic intermediates that temporarily accumulate. Consistent with this, dimethylethanolamine was shown to be another new growth substrate, but monomethylethanolamine was not. The specific methanogen inhibitor 2-bromoethanesulfonate (BES) inhibited methane production from choline. When choline and trimethylamine are provided together, diauxic growth occurs, with trimethylamine being utilized first, and then after a lag (∼7 days) choline is metabolized. Three type strains of Methanococcoides (M. methylutens, M. burtonii, and M. alaskense), in contrast, did not utilize choline. However, two of them (M. methylutens and M. burtonii) did metabolize dimethylethanolamine. These results extend the known substrates that can be directly utilized by some methanogens, giving them the advantage that they would not be reliant on bacterial syntrophs for their substrate supply.