Modern cellular RNA polymerases and ribosomes are gigantic, multiple-subunit complexes, and they mutually synthesize each other at the core of the gene expression system. How such complicated molecules and systems emerged remains a fundamental mystery in molecular biology. Conservation of protein structures provides essential information to elucidate such ancient evolutionary events, as structures are more conserved than sequences. In this review, we showcase the conserved protein structures within RNA polymerase and ribosomes and present our recent experimental findings on the evolutionary relationships between ancient β-barrels, thereby shedding light on the common origin of RNA polymerase and multiple ribosomal proteins.