Gardnerella vaginalis produces cytolysin vaginolysin (VLY), which has been suggested to be a contributor to bacterial vaginosis pathogenesis. VLY along with intermedilysin (ILY) from Streptococcus intermedius have been attributed to a group of cholesterol-dependent cytolysins (CDCs) whose pore-forming activity depends on human CD59 (hCD59). Here, we show that different types of cells lacking hCD59 are susceptible to VLY-mediated lysis, albeit to different extents. We analyze the effects of both hCD59 and cholesterol on VLY cytolytic activity. We show that VLY binds to cholesterol-rich membranes of non-human cells, while VLY with an impaired cholesterol recognition site retains binding to the hCD59-containing cells. We further demonstrate that cholesterol binding by VLY is sufficient to trigger the formation of oligomeric complexes on cholesterol rich-liposomes lacking hCD59. Thus, VLY may induce cell lysis following two alternative pathways. One requires only cholesterol and does not depend on hCD59. The second pathway involves hCD59 contribution similarly to ILY. Apparently, under physiological conditions VLY acts in the most effective way by accepting the assistance of hCD59.