Bacterial vaginosis (BV) is a common, recurrent vaginal infection linked to increased chances of preterm delivery, incidence of sexually transmitted infections and fertility problems. BV is caused by a shift of the vaginal ecosystem from predominately Lactobacillus to a multispecies Actinomyces biofilm with the most common representatives identified as Gardnerella vaginalis and Prevotella spp. Current treatments have been associated with increased resistance as well as negative effects on healthy microbiota. The objective of this study was to evaluate the synergistic potential of ten two-antimicrobial combinations against G. vaginalis and four representative lactobacilli. The four tested antimicrobials were lauramide arginine ethyl ester, ε-poly-L-lysine, clindamycin phosphate, metronidazole and the bacteriocin subtilosin A. The use of bacteriocins as either synergist or alternative treatment positions bacteriocins as an excellent alternative to current antibiotics. The microdilution method was used to determine the minimum inhibitory concentration (MIC) of each of the antimicrobials individually, and the checkerboard assay was used to evaluate these MICs in combination. Clindamycin and subtilosin (CS), and metronidazole and subtilosin were synergistic against G. vaginalis in terms of fractional inhibitory concentration index (FICI). All tested combinations were found to have Bliss synergy. The combination of clindamycin and polylysine (CP) was identified as antagonistic against L. acidophilus in terms of both FICI and Bliss synergy. The combination of clindamycin and metronidazole (CM) was antagonistic against L. vaginalis for both FICI and Bliss synergy. The combinations of CP, clindamycin and LAE, CS, and LAE and polylysine were identified as Bliss antagonistic against L. vaginalis but did not indicate FICI antagonism.