Background: Bacterial vaginosis (BV) is the most common vaginal disorder of reproductive-age women. Yet the cause of BV has not been established. To uncover key determinants of BV, we employed a multi-omic, systems-biology approach, including both deep 16S rRNA gene-based sequencing and metabolomics of lavage samples from 36 women. These women varied demographically, behaviorally, and in terms of health status and symptoms. Principal Findings: 16S rRNA gene-based community composition profiles reflected Nugent scores, but not Amsel criteria. In contrast, metabolomic profiles were markedly more concordant with Amsel criteria. Metabolomic profiles revealed two distinct symptomatic BV types (SBVI and SBVII) with similar characteristics that indicated disruption of epithelial integrity, but each type was correlated to the presence of different microbial taxa and metabolites, as well as to different host behaviors. The characteristic odor associated with BV was linked to increases in putrescine and cadaverine, which were both linked to Dialister spp. Additional correlations were seen with the presence of discharge, 2-methyl-2-hydroxybutanoic acid, and Mobiluncus spp., and with pain, diethylene glycol and Gardnerella spp. Conclusions: The results not only provide useful diagnostic biomarkers, but also may ultimately provide much needed insight into the determinants of BV.