Neisseria meningitis is a human commensal bacterium that occasionally causes life-threatening disease. As with a number of other bacterial pathogens, meningococcal populations comprise distinct lineages, which persist over many decades and during global spread in the face of high rates of recombination. In addition, the propensity to cause invasive disease is associated with particular "hyperinvasive" lineages that coexist with less invasive lineages despite the fact that disease does not contribute to host-to-host transmission. Here, by combining a modeling approach with molecular epidemiological data from 1,108 meningococci isolated in the Czech Republic over 27 years, we show that interstrain competition, mediated by immune selection, can explain both the persistence of multiple discrete meningococcal lineages and the association of a subset of these with invasive disease. The model indicates that the combinations of allelic variants of housekeeping genes that define these lineages are associated with very small differences in transmission efficiency among hosts. These findings have general implications for the emergence of lineage structure and virulence in recombining bacterial populations.