The emergence and spread of antimicrobial resistance in Neisseria gonorrhoeae (GC) underline the need of “antibiotic-free” strategies for the control of gonorrhea. The aim of this study was to assess the anti-gonococcal activity of 14 vaginal Lactobacillus strains, belonging to different species (L. crispatus, L. gasseri, L. vaginalis), isolated from healthy pre-menopausal women. In particular, we performed “inhibition” experiments, evaluating the ability of both lactobacilli cells and culture supernatants in reducing GC viability, at two different contact times (7 and 60 min). First, we found that the acidic environment, associated to lactobacilli metabolism, is extremely effective in counteracting GC growth, in a pH- and time-dependent manner. Indeed, a complete abolishment of GC viability by lactobacilli supernatants was observed only for pH values < 4.0, even at short contact times. On the contrary, for higher pH values, no 100%-reduction of GC growth was reached at any contact time. Experiments with organic/inorganic acid solutions confirmed the strict correlation between the pH levels and the anti-gonococcal effect. In this context, the presence of lactate seemed to be crucial for the anti-gonococcal activity, especially for pH values in the range 4.4–5.3, indicating that the presence of H+ ions is necessary but not sufficient to kill gonococci. Moreover, experiments with buffered supernatants led to exclude a direct role in the GC killing by other bioactive molecules produced by lactobacilli. Second, we noticed that lactobacilli cells are able to reduce GC viability and to co-aggregate with gonococci. In this context, we demonstrated that released-surface components with biosurfactant properties, isolated from “highly-aggregating” lactobacilli, could affect GC viability. The antimicrobial potential of biosurfactants isolated from lactobacilli against pathogens has been largely investigated, but this is the first report about a possible use of these molecules in order to counteract GC infectivity. In conclusion, we identified specific Lactobacillus strains, mainly belonging to L. crispatus species, able to counteract GC viability through multiple mechanisms. These L. crispatus strains could represent a new potential probiotic strategy for the prevention of GC infections in women.