Strain structure is a well-documented phenomenon in many pathogenic and commensal bacterial species, where distinct strains persist over time exhibiting stable associations between genetic or phenotypic traits. This structure is surprising, particularly in highly recombinogenic species like Streptococcus pneumoniae} because recombination typically breaks down linkage disequilibrium, the non-random association of alleles at different loci. Allelic diversity is a necessary condition of strain structure. Recent work suggests that multi-locus negative frequency-dependent selection (NFDS) acts to maintain diversity across bacterial genomes. Here, using modelling and genomic analysis, we show that multi-locus NFDS also shapes bacterial strain structure through emergent epistatic effects. We develop models of two NFDS mechanisms -- metabolic niche differentiation and competition-colonisation trade-offs -- and show that epistasis emerges readily in these models. Notably, both models generate frequency-dependent epistasis. Unlike classical epistasis, this acts to either reinforce or abolish existing strain structure, making observed allele associations contingent on the evolutionary history of the population. We then use a dataset of over 3000 S. pneumoniae genomes to test our model predictions, and make observations consistent with emerging epistatic effects on gene associations. Our results extend and generalise previous work on the role of antigen-specific acquired immunity (a diversity-maintaining mechanism) on strain structure. Overall, this works contributes to a better understanding of the evolutionary processes shaping the structure of bacterial populations, which is central to predictive modelling of multi-strain pathogens