The origin of eukaryotes is one of the hardest problems in evolutionary biology and sometimes raises the ominous specter of irreducible complexity. Reconstruction of the gene repertoire of the last eukaryotic common ancestor (LECA) has revealed a highly complex organism with a variety of advanced features but no detectable evolutionary intermediates to explain their origin. Recently, however, genome analysis of diverse archaea led to the discovery of apparent ancestral versions of several signature eukaryotic systems, such as the actin cytoskeleton and the ubiquitin network, that are scattered among archaea. These findings inspired the hypothesis that the archaeal ancestor of eukaryotes was an unusually complex form with an elaborate intracellular organization. The latest striking discovery made by deep metagenomic sequencing vindicates this hypothesis by showing that in phylogenetic trees eukaryotes fall within a newly identified archaeal group, the Lokiarchaeota, which combine several eukaryotic signatures previously identified in different archaea. The discovery of complex archaea that are the closest living relatives of eukaryotes is most compatible with the symbiogenetic scenario for eukaryogenesis.