Clostridium difficile infection (CDI) is characterized by dysbiosis of the intestinal microbiota and a profound derangement in the fecal metabolome. However, the contribution of specific gut microbes to fecal metabolites in C. difficile-associated gut microbiome remains poorly understood. Using gas-chromatography mass spectrometry (GC-MS) and 16S rRNA deep sequencing, we analyzed the metabolome and microbiome of fecal samples obtained longitudinally from subjects with Clostridium difficile infection (n = 7) and healthy controls (n = 6). From 155 fecal metabolites, we identified two sterol metabolites at >95% match to cholesterol and coprostanol that significantly discriminated C. difficile-associated gut microbiome from healthy microbiota. By correlating the levels of cholesterol and coprostanol in fecal extracts with 2,395 bacterial operational taxonomic units (OTUs) determined by 16S rRNA sequencing, we identified 63 OTUs associated with high levels of coprostanol and 2 OTUs correlated with low coprostanol levels. Using indicator species analysis (ISA), 31 of the 63 coprostanol-associated bacteria correlated with health, and two Veillonella species were associated with low coprostanol levels that correlated strongly with CDI. These 65 bacterial taxa could be clustered into 12 sub-communities, with each community containing a consortium of organisms that co-occurred with one another. Our studies identified 63 human gut microbes associated with cholesterol-reducing activities. Given the importance of gut bacteria in reducing and eliminating cholesterol from the GI tract, these results support the recent finding that gut microbiome may play an important role in host lipid metabolism.