We reconstructed a global tree of life (ToL) with non-reversible and non-stationary models of genome evolution that root trees intrinsically. We implemented Bayesian model selection tests and compared the statistical support for four conflicting ToL hypotheses. We show that reconstructions obtained with a Bayesian implementation (Klopfstein et al., 2015) are consistent with reconstructions obtained with an empirical Sankoff parsimony (ESP) implementation (Harish et al., 2013). Both are based on the genome contents of coding sequences for protein domains (superfamilies) from hundreds of genomes. Thus, we conclude that the independent descent of Eukaryotes and Akaryotes (archaea and bacteria) from the universal common ancestor (UCA) is the most probable as well as the most parsimonious hypothesis for the evolutionary origins of extant genomes. Reconstructions of ancestral proteomes by both Bayesian and ESP methods suggest that at least 70% of unique domain-superfamilies known in extant species were present in the UCA. In addition, identification of a vast majority (96%) of the mitochondrial superfamilies in the UCA proteome precludes a symbiotic hypothesis for the origin of eukaryotes. Accordingly, neither the archaeal origin of eukaryotes nor the bacterial origin of mitochondria is supported by the data. The proteomic complexity of the UCA suggests that the evolution of cellular phenotypes in the two primordial lineages, Akaryotes and Eukaryotes, was driven largely by duplication of common superfamilies as well as by loss of unique superfamilies. Finally, innovation of novel superfamilies has played a surprisingly small role in the evolution of Akaryotes and only a marginal role in the evolution of Eukaryotes.