Bacterial vaginosis (BV) is characterized by a reduction in Lactobacillus (L.) spp. abundance and increased abundance of facultative anaerobes, such as Gardnerella spp. BV aetiology is not fully understood; however, bacteriophages could play a pivotal role in the perturbation of the vaginal bacterial community. We investigated the vaginal viral community, including bacteriophages and the association to the bacterial community and BV-status. Vaginal samples from 48 patients undergoing IVF treatment for non-female factor infertility were subjected to metagenomic sequencing of purified virus-like particles. The vaginal viral community was characterized and correlated with the BV-status by Nugent score, bacterial community, structure, and the presence of key vaginal bacterial species. The majority of identified vaginal viruses belonged to the class of double-stranded DNA bacteriophages, with eukaryotic viruses constituting 4% of the total reads. Clear links between the viral community composition and BV (q = 0.006, R = 0.26) as well as the presence of L. crispatus (q = 0.001, R = 0.43), L. iners, Gardnerella spp., and Atopobium vaginae were found (q < 0.002, R > 0.15). The eukaryotic viral community also correlated with BV-status (q = 0.018, R = 0.20). In conclusion, the vaginal virome was clearly linked with bacterial community structure and BV-status.