Most Sternorrhynchan insects house endosymbiotic bacteria that aid their host insects by providing essential nutrients not found in the host diet, in exchange for living space. We used molecular systematics to identify the endosymbiotic bacteria living inside armored scale insects and investigated the extent of coevolution that has occurred in this group. Bacterial identification was completed using 16S rDNA sequence data. Endosymbionts of the Diaspididae were found to be in the Bacteriodetes, closely related to male-killing bacteria found in ladybird beetles, and Candidatus Blattabacterium sp., primary endosymbionts of cockroaches. Additionally, 23S rDNA from the bacteria was sequenced, concatenated with 16S data and phylogenetically analyzed. These data were compared with phylogenetically analyzed host DNA sequence data from two genes, 28S and Elongation factor 1-alpha. The total data set included over eighty host species and their endosymbionts. Comparing phylogenetic trees of host and bacteria resulted in nearly congruent evolutionary histories. We discuss evolutionary implications of the relationship between armored scale insects and their endosymbionts.