Gut microbiota metabolization of dietary choline may promote atherosclerosis through trimethylamine (TMA), which is rapidly absorbed and converted in the liver to proatherogenic trimethylamine-N-oxide (TMAO). The aim of this study was to verify whether TMAO urinary levels may be associated with the fecal relative abundance of specific bacterial taxa and the bacterial choline TMA-lyase gene cutC. The analysis of sequences available in GenBank grouped the cutC gene into two main clusters, cut-Dd and cut-Kp. A quantitative real-time polymerase chain reaction (qPCR) protocol was developed to quantify cutC and was used with DNA isolated from three fecal samples collected weekly over the course of three consecutive weeks from 16 healthy adults. The same DNA was used for 16S rRNA gene profiling. Concomitantly, urine was used to quantify TMAO by ultra-performance liquid chromatography coupled with tandem mass spectrometry (UPLC-MS/MS). All samples were positive for cutC and TMAO. Correlation analysis showed that the cut-Kp gene cluster was significantly associated with Enterobacteriaceae. Linear mixed models revealed that urinary TMAO levels may be predicted by fecal cut-Kp and by 23 operational taxonomic units (OTUs). Most of the OTUs significantly associated with TMAO were also significantly associated with cut-Kp, confirming the possible relationship between these two factors. In conclusion, this preliminary method-development study suggests the existence of a relationship between TMAO excreted in urine, specific fecal bacterial OTUs, and a cutC subgroup ascribable to the choline-TMA conversion enzymes of Enterobacteriaceae.