Proteins come at a most amazing diversity of structures and functions: they perform transportation (e.g. haemoglobin), provide stability (cytoskeleton or muscles), harvest energy (photosynthesis) and confer signals (cell division) in all organisms. No proteins, no life. Rational and irrational lab based as well as computational techniques have tried for decades now to create proteins with desired properties but with meager success at best. Also, how evolution accomplished protein diversity, is largely unclear, after many decades of research. This lack of knowledge hampers further progress in exploiting evolutionary strategies for designing new proteins since, for example, directed evolution gets easily stuck due to constraints imposed by historic contingencies of the starting material. We therefore address two fundamental questions: (i) how did enzymes change their relative functionalities (i.e. dominant vs. promiscous sub-dominant activities) during evolution and (ii) is it possible to generate completely new, functional proteins out of random amino-acid sequences. For the former we use phylogenies, ancestral sequence reconstruction and novel surface display methods in combination with droplet assays to screen billions of mutants from large libraries within hours. For the latter we reconstruct the history of how novel proteins were borne out from random DNA and became functional without selection and adaptation of their structural properties. Together, our methods will open new avenues for protein design which can overcome (at least some of the) hurdles imposed by earlier, more directed strategies.