Bacterial vaginosis (BV) is a vaginal anaerobic dysbiosis that affects women of reproductive age worldwide. BV is microbiologically characterized by the depletion of vaginal lactobacilli and the overgrowth of anaerobic bacterial species. Accumulated evidence suggests that Gardnerella spp. have a pivotal role among BV-associated bacteria in the initiation and development of BV. However, Gardnerella spp. often colonize healthy women. Lactobacillus iners is considered as a prevalent constituent of healthy vaginal microbiota, and is abundant in BV. Gardnerella spp. and L. iners secrete the toxins vaginolysin (VLY) and inerolysin (INY), which have structural and activity features attributed to cholesterol-dependent cytolysins (CDCs). CDCs are produced by many pathogenic bacteria as virulence factors that participate in various stages of disease progression by forming lytic and non-lytic pores in cell membranes or via pore-independent pathways. VLY is expressed in the majority of Gardnerella spp. isolates; less is known about the prevalence of the gene that encodes INY. INY is a classical CDC; membrane cholesterol acts a receptor for INY. VLY uses human CD59 as its receptor, although cholesterol remains indispensable for VLY pore-forming activity. INY-induced damage of artificial membranes is directly dependent on cholesterol concentration in the bilayer, whereas VLY-induced damage occurs with high levels of membrane cholesterol (>40 mol%). VLY primarily forms membrane-embedded complete rings in the synthetic bilayer, whereas INY forms arciform structures with smaller pore sizes. VLY activity is high at elevated pH, which is characteristic of BV, whereas INY activity is high at more acidic pH, which is specific for a healthy vagina. Increased VLY levels in vaginal mucosa in vivo were associated with clinical indicators of BV. However, experimental evidence is lacking for the specific roles of VLY and INY in BV. The interplay between vaginal bacterial species affects the expression of the gene encoding VLY, thereby modulating the virulence of Gardnerella spp. This review discusses the current evidence for VLY and INY cytolysins, including their structures and activities, factors affecting their expression, and their potential impacts on the progression of anaerobic dysbiosis.