Woese and Fox's 1977 paper on the discovery of the Archaea triggered a revolution in the field of evolutionary biology by showing that life was divided into not only prokaryotes and eukaryotes. Rather, they revealed that prokaryotes comprise two distinct types of organisms, the Bacteria and the Archaea. In subsequent years, molecular phylogenetic analyses indicated that eukaryotes and the Archaea represent sister groups in the tree of life. During the genomic era, it became evident that eukaryotic cells possess a mixture of archaeal and bacterial features in addition to eukaryotic-specific features. Although it has been generally accepted for some time that mitochondria descend from endosymbiotic alphaproteobacteria, the precise evolutionary relationship between eukaryotes and archaea has continued to be a subject of debate. In this Review, we outline a brief history of the changing shape of the tree of life and examine how the recent discovery of a myriad of diverse archaeal lineages has changed our understanding of the evolutionary relationships between the three domains of life and the origin of eukaryotes. Furthermore, we revisit central questions regarding the process of eukaryogenesis and discuss what can currently be inferred about the evolutionary transition from the first to the last eukaryotic common ancestor.