The essential nutrient choline is metabolized by gut bacteria to the disease-associated metabolite trimethylamine (TMA). However, most of the choline obtained via the diet and present in the human body is incorporated into larger metabolites, including the lipid phosphatidylcholine (PC). Here, we report that many choline-utilizing gut microorganisms can hydrolyse PC using a phospholipase D (PLD) enzyme and further convert the released choline to TMA. Genetic and in vitro characterization of the PLD from Escherichia coli MS 200-1 showed this enzyme is essential for bacterial hydrolysis of PC and prefers this substrate. PLDs are also found in gut bacterial isolates that are unable to convert choline to TMA, suggesting that additional members of the gut microbiota may influence access to this substrate. Unexpectedly, this PLD is only distantly related to characterized PLDs from pathogenic bacteria, suggesting a distinct evolutionary history. Together, these results reveal a previously underappreciated role for gut microorganisms in phospholipid metabolism and a potential target for inhibiting TMA production.