The leafhopper subfamily Cicadellinae is the most diverse lineage of xylem-feeding herbivores and some of its members (=sharpshooters) are major vectors of bacterial diseases of economically important plants. Many insects utilizing deficient diets, such as the extremely dilute xylem-sap, are associated with bacterial endosymbionts, which provide their hosts with missing essential nutrients. Symbionts are vertically transmitted to progeny and may reside within specialized host cells (bacteriocytes). In sharpshooters, these are clustered in paired organs in the abdominal cavity, called bacteriomes. Sharpshooters harbor two distinct types of symbionts in their bacteriomes: Candidatus Baummania cicadellinicola, previously known from five host species, and a symbiont in the Bacteroidetes phylum, previously known from a single species. In the present study the 16S rDNA gene was sequenced for both symbiont types and partial COI, COII, Histone H3, and 16S rDNA sequences were obtained for sharpshooter and related leafhoppers hosts. Both symbionts occurred in most (Baumannia) or all (Bacteroidetes symbiont) of the 29 sharpshooter species examined. Phylogenetic analyses and searching of sequence databases revealed that both symbiont types form highly supported clades within their respective phyla. Topologies and datasets for both symbionts show statistical congruence with the host phylogeny based on an event-based tree-fitting method, Shimodaira-Hasegawa, and ILD tests. Assuming a shared coevolutionary history among symbionts and hosts, Baumannia symbionts show about 5 times greater rates of substitution in their 16S rDNA than the Bacteroidetes symbionts. These findings support an ancient history of vertical transmission of both symbiont types, strongly suggesting an obligate association with both.