The origin of eukaryotes represents one of the most significant events in evolution, since it allowed the posterior emergence of multicellular organisms1,2. Evolutionary biologists have tried to unveil the mechanism leading to eukaryotes, most likely the symbiosis between two previously unrelated organisms3. Yet, it remains unclear how the genetic architecture of life was transformed to allow this increase in complexity. Here, we try to fill this gap by studying the size distributions of genes and their corresponding proteins in 6,519 species across the tree of life. We find a scale-invariant relationship between gene mean length and variance, with clades appearing in evolutionary order. Our analysis unveils a common multiplicative process of gene growth along evolution, but reveals a phase transition corresponding with the emergence of the eukaryotic cell. Proteins and genes grow in parallel in prokaryotes. However, the number of constraints in order to have a protein with the right three-dimensional structure increases very fast with its length. This increasing computational difficulty eventually gave way to a new phase as happens in the phase transitions of certain search algorithms4-6. This new regulatory phase is characterized by the incorporation of gene non-coding sequences7-9, in agreement with the introns-late model8. Our approach allows us to predict not only the macroscopic details underlying the emergence of eukaryotes (e.g., the rate and shape of this evolutionary innovation), but the timing of this event.