Women-who-have-sex-with-women (WSW) are at increased risk of bacterial vaginosis (BV). We investigated the impact of practices and past BV on the vaginal microbiota within a two-year longitudinal cohort of Australian WSW. Self-collected vaginal swabs were used to characterise the vaginal microbiota using 16S-rRNA gene sequencing. Hierarchical clustering defined community state types (CSTs). Bacterial diversity was calculated using the Shannon diversity index and instability of the vaginal microbiota was assessed by change of CST and Bray-Curtis dissimilarity. Sex with a new partner increased the bacterial diversity (adjusted-coefficient = 0.41, 95%CI: 0.21,0.60, p < 0.001) and instability of the vaginal microbiota, in terms of both change of CST (adjusted-odds-ratio = 2.65, 95%CI: 1.34,5.22, p = 0.005) and increased Bray-Curtis dissimilarity (adjusted-coefficient = 0.21, 95%CI: 0.11,0.31, p < 0.001). Women reporting sex with a new partner were more likely than women reporting no new partner to have a vaginal microbiota characterised by Gardnerella vaginalis (adjusted-relative-risk-ratio[aRRR] = 3.45, 95%CI: 1.42,8.41, p = 0.006) or anaerobic BV-associated bacteria (aRRR = 3.62, 95%CI: 1.43,9.14, p = 0.007) relative to a Lactobacillus crispatus dominated microbiota. Sex with a new partner altered the vaginal microbiota of WSW by increasing the diversity and abundance of BV-associated bacteria. These findings highlight the influence of practices on the development of a non-optimal vaginal microbiota and provide microbiological support for the sexual exchange of bacteria between women.