Bacterial vaginosis (BV) is a common syndrome associated with numerous adverse health outcomes in women. Despite its medical importance, the etiology and microbial ecology of BV remain poorly understood. We used broad-range PCR to census the community structure of the healthy and BV-affected vaginal microbial ecosystems and synthesized current publicly available bacterial 16S rRNA gene sequence data from this environment. The community of vaginal bacteria detected in subjects with BV was much more taxon rich and diverse than in subjects without BV. At a 97% sequence similarity cutoff, the number of operational taxonomic units (OTUs) per patient in 28 subjects with BV was nearly three times greater than in 13 subjects without BV: 14.8 ± 0.7 versus 5.2 ± 0.75 (mean ± standard error). OTU-based analyses revealed previously hidden diversity for many vaginal bacteria that are currently poorly represented in GenBank. Our sequencing efforts yielded many novel phylotypes (123 of our sequences represented 38 OTUs not previously found in the vaginal ecosystem), including several novel BV-associated OTUs, such as those belonging to the Prevotella species complex, which remain severely underrepresented in the current NCBI database. Community composition was highly variable among subjects at a fine taxonomic scale, but at the phylum level, Actinobacteria and Bacteroidetes were strongly associated with BV. Our data describe a previously unrecognized extent of bacterial diversity in the vaginal ecosystem. The human vagina hosts many bacteria that are only distantly related to known species, and subjects with BV harbor particularly taxon-rich and diverse bacterial communities.