No accepted phylogenetic scheme for prokaryotes emerged until the late 1970s. Prior to that, it was assumed that there was a phylogenetic tree uniting all prokaryotes, but no suitable data were available for its construction. For 20 years, through the 1980s and 1990s, rRNA phylogenies were the gold standard. However, beginning in the last decade, findings from genomic data have challenged this new consensus. Gene trees can conflict greatly, and strains of the same species can differ enormously in genome content. Horizontal gene transfer is now known to be a significant influence on genome evolution. The next decade is likely to resolve whether or not we retain the centuries-old metaphor of the tree for all of life.