Endosymbioses are a major form of biological complexity affecting the ecological and evolutionary diversification of many eukaryotic groups. These associations are exemplified by nutritional symbioses of insects for which phylogenetic studies have demonstrated numerous cases of long-term codiversification between a bacterial and a host lineage. Some insects, including most leafhoppers (Insecta: Hemiptera: Cicadellidae), have more than one bacterial symbiont within specialized host cells, raising questions regarding the patterns of codiversification of these multiple partners and the evolutionary persistence of complex symbiotic systems. Previous studies reported the presence of two dominant symbiont types in a member of the leafhopper subfamily Cicadellinae (sharpshooters). In this study, 16S rRNA sequences were obtained and used to examine the occurrence and evolutionary relationships of the two dominant symbiont types across 29 leafhopper species. Candidatus Sulcia muelleri (Bacteroidetes) was detected in all leafhopper species examined, a finding that is consistent with a previous report of its ancient association with the Auchenorrhyncha (a grouping that includes leafhoppers, treehoppers, cicadas, planthoppers, and spittlebugs). Baumannia cicadellinicola (Proteobacteria), previously known from only five sharpshooter species, was found only in the sharpshooter tribes Cicadellini and Proconiini, as well as in the subfamily Phereurhininae. Mitochondrial and nuclear gene sequences were obtained and used to reconstruct host phylogenies. Analyses of host and symbiont data sets support a congruent evolutionary history between sharpshooters, Sulcia and Baumannia and thus provide the first strong evidence for long-term co-inheritance of multiple symbionts during the diversification of a eukaryotic host. Sulcia shows a fivefold lower rate of 16S rDNA sequence divergence than does Baumannia for the same host pairs. The term 'coprimary' symbiont is proposed for such cases.