The aetiology of bacterial vaginosis (BV) is not well-understood, and prevalence appears to be higher among women living in sub-Saharan Africa. A recent conceptual model implicates three main bacteria (Gardnerella vaginalis; Atopobium vaginae; and Prevotella bivia), sexual activity, sialidase activity, and biofilm formation in the pathogenesis of BV. We describe the vaginal microbiota, presence of the putative sialidase A gene of G. vaginalis, and biofilm among 386 adolescent girls aged 17 and 18 years in a cross-sectional study in Mwanza, Tanzania around the time of expected sexual debut. Vaginal swabs were collected and tested by quantitative polymerase chain reaction (qPCR) for five Lactobacillus species, G. vaginalis, A. vaginae, P. bivia, the sialidase A gene of G. vaginalis, and by fluorescence in situ hybridisation (FISH) for evidence of G. vaginalis and A. vaginae biofilm. We conducted a risk factor analysis of G. vaginalis, A. vaginae and P. bivia, and explored the associations between biofilm, the presence of the sialidase A gene, and non-optimal vaginal microbiota (Nugent 4-7). L. crispatus and L. iners were detected in 69 and 82% of girls, respectively. The prevalence of L. crispatus was higher than previously reported in earlier studies among East and Southern African women. G. vaginalis, A. vaginae, P. bivia were independently associated with reported penile-vaginal sex. Samples with all three BV-associated bacteria made up the highest proportion of samples with Nugent-BV compared to samples with each bacterium alone or together in pairs. Of the 238 girls with G. vaginalis, 63% had the sialidase A gene detected, though there was no difference by reported sexual activity (p = 0.197). Of the 191 girls with results for sialidase A gene and FISH, there was strong evidence for an increased presence of sialidase A gene among those with evidence of a biofilm (p < 0.001). There was a strong association between biofilm and non-optimal microbiota (aOR67.00; 95% CI 26.72-190.53). These results support several of the steps outlined in the conceptual model, although the role of sexual activity is less clear. We recommend longitudinal studies to better understand changes in vaginal microbiota and biofilm formation around the time of sexual debut.