Of the three domains of life, the Archaea are the most recently discovered and, from the perspective of systematics, perhaps the least understood. More than three decades after their discovery, there is still no overwhelming consensus as to their phylogenetic status, with diverse evidence supporting in varying degrees their monophyly, paraphyly, or even polyphyly. As a further complication, their evolutionary history is inextricably linked to the origin of Eukarya, one of the most challenging problems in evolutionary biology. This exclusive relationship between the eukaryal nucleocytoplasm and the Archaea is further supported by a new methodology for rooting the ribosomal Tree of Life based on amino acid composition. Novel approaches such as utilizing horizontal gene transfers as synchronizing events and branch length analysis of deep paralogs will help to clarify temporal relationships between these lineages, and may prove useful in evaluating the numerous conflicting hypotheses related to the evolution of the Archaea and Eukarya. © 2010 Institut Pasteur. Published by Elsevier SAS. All rights reserved.