Iceryine scale insects (Hemiptera: Margarodidae: Iceryini) are an unusual and important group of insects. The tribe is made up of about 90 species in six genera found worldwide and many species are known to display very unusual genetic systems, including the only known case of hermaphroditism in the Class Insecta. A phylogenetic reconstruction was undertaken of 40 taxa from 5 genera using close to 2200 base pairs from 3 genes, both ribosomal (18S and 28S) and protein coding (wingless), and 40 morphological characters from adult females and first-instar nymphs. This analysis recovered some surprising results, including non-monophyletic genera. Two of the largest genera, Icerya Signoret and Steatococcus Ferris are not monophyletic. But the Australian genus Auloicerya Morrison made up of two species is the only genus recovered as a monophyletic group in our analysis. Gueriniella Fernald, a genus represented by one species in this reconstruction, is sister to all other iceryine species. These phylogenetic relationships correspond more closely with biogeographical patterns than with current classification. For example, Steatococcus, Icerya and Crypticerya species found in the United States are more closely related to one another than to other species in their respective genera.