Mealybugs (Coccoidea: Pseudococcidae) are sap-sucking plant parasites that harbor bacterial endosymbionts within specialized organs. Previous studies have identified two subfamilies, Pseudococcinae and Phenacoccinae, within mealybugs and determined the primary endosymbionts (P-endosymbionts) of the Pseudococcinae to be Betaproteobacteria ("Candidatus Tremblaya princeps") containing Gammaproteobacteria secondary symbionts. Here, the P-endosymbionts of phenacoccine mealybugs are characterized based on 16S rRNA from the bacteria of 20 species of phenacoccine mealybugs and four outgroup Puto species (Coccoidea: Putoidae) and aligned to more than 100 published 16S rRNA sequences from symbiotic and free-living bacteria. Phylogenetic analyses recovered three separate lineages of bacteria from the Phenacoccinae, and these are considered to be the P-endosymbionts of their respective mealybug hosts, with those from (i) the mealybug genus Rastrococcus belonging to the Bacteroidetes, (ii) the subterranean mealybugs, tribe Rhizoecini, also within Bacteroidetes, in a clade sister to cockroach endosymbionts (Blattabacterium), and (iii) the remaining Phenacoccinae within the Betaproteobacteria, forming a well-supported sister group to "Candidatus Tremblaya princeps." Names are proposed for two strongly supported lineages: "Candidatus Brownia rhizoecola" for P-endosymbionts of Rhizoecini and "Candidatus Tremblaya phenacola" for P-endosymbionts of Phenacoccinae excluding Rastrococcus and Rhizoecini. Rates of nucleotide substitution among lineages of Tremblaya were inferred to be significantly faster than those of free-living Betaproteobacteria. Analyses also recovered a clade of Gammaproteobacteria, sister to the P-endosymbiont lineage of aphids ("Candidatus Buchnera aphidicola"), containing the endosymbionts of Putoidae, the secondary endosymbionts of pseudococcine mealybugs, and the endosymbionts of several other insect groups.