The interaction between gut bacterial and viral microbiota is thought to be important in human health. While fluctuations in female genital tract (FGT) bacterial microbiota similarly determine sexual health, little is known about the presence, persistence, and function of vaginal bacteriophages. We conducted shotgun metagenome sequencing of cervicovaginal samples from South African adolescents collected longitudinally, who received no antibiotics. We annotated viral reads and circular bacteriophages, identified CRISPR loci and putative prophages, and assessed their diversity, persistence, and associations with bacterial microbiota composition. Siphoviridae was the most prevalent bacteriophage family, followed by Myoviridae, Podoviridae, Herelleviridae, and Inoviridae. Full-length siphoviruses targeting bacterial vaginosis (BV)-associated bacteria were identified, suggesting their presence in vivo. CRISPR loci and prophage-like elements were common, and genomic analysis suggested higher diversity among Gardnerella than Lactobacillus prophages. We found that some prophages were highly persistent within participants, and identical prophages were present in cervicovaginal secretions of multiple participants, suggesting that prophages, and thus bacterial strains, are shared between adolescents. The number of CRISPR loci and prophages were associated with vaginal microbiota stability and absence of BV. Our analysis suggests that (pro)phages are common in the FGT and vaginal bacteria and (pro)phages may interact.