Background: A vaginal microbiota dominated by lactobacilli (particularly Lactobacillus crispatus) is associated with vaginal health, whereas a vaginal microbiota not dominated by lactobacilli is considered dysbiotic. Here we investigated whether L. crispatus strains isolated from the vaginal tract of women with Lactobacillus-dominated vaginal microbiota (LVM) are pheno- or genotypically distinct from L. crispatus strains isolated from vaginal samples with dysbiotic vaginal microbiota (DVM). Results: We studied 33 L. crispatus strains (n = 16 from LVM; n = 17 from DVM). Comparison of these two groups of strains showed that, although strain differences existed, both groups degraded various carbohydrates, produced similar amounts of organic acids, inhibited Neisseria gonorrhoeae growth, and did not produce biofilms. Comparative genomics analyses of 28 strains (n = 12 LVM; n = 16 DVM) revealed a novel, 3-fragmented glycosyltransferase gene that was more prevalent among strains isolated from DVM. Most L. crispatus strains showed growth on glycogen-supplemented growth media. Strains that showed less-efficient (n = 6) or no (n = 1) growth on glycogen all carried N-terminal deletions (respectively, 29 and 37 amino acid deletions) in a putative pullulanase type I protein. Discussion: L. crispatus strains isolated from LVM were not phenotypically distinct from L. crispatus strains isolated from DVM; however, the finding that the latter were more likely to carry a 3-fragmented glycosyltransferase gene may indicate a role for cell surface glycoconjugates, which may shape vaginal microbiota-host interactions. Furthermore, the observation that variation in the pullulanase type I gene is associated with growth on glycogen discourages previous claims that L. crispatus cannot directly utilize glycogen.