Gardnerella vaginalis is the most common species found in bacterial vaginosis (BV). However, it is also present in a significant proportion of healthy women and G. vaginalis vaginal colonization does not always lead to BV. In an effort to better understand the differences between G. vaginalis isolated from women with a positive (BV) versus a negative (non-BV) diagnosis of BV, we compared the virulence potential of 7 BV and 7 non-BV G. vaginalis isolates and assessed the virulence factors related to biofilm formation, namely: initial adhesion and cytotoxic effect, biofilm accumulation, susceptibility to antibiotics, and transcript levels of the known vaginolysin, and sialidase genes. Furthermore, we also determined the ability of G. vaginalis to displace lactobacilli previously adhered to HeLa cells. Our results showed that non-BV strains were less virulent than BV strains, as suggested by the lower cytotoxicity and initial adhesion to Hela cells. Significant differences in expression of known virulence genes were also detected, further suggesting a higher virulence potential of the BV associated G. vaginalis. Importantly, we demonstrated that BV associated G. vaginalis were able to displace pre-coated vaginal protective lactobacilli and we hypothesize this to be a trigger for BV development.