Proteins are surreptitious cellular agents: while robust against mutations they are very evolvable; most are marginally stable and dynamic but others form a stable cellular matrix. Some genes seem to have emerged de novo from random pieces of genomic DNA, others may have been around for billions of years, virtually unchanged. Genomic and structural data provide new insights on how proteins came such a long way, probably from an initially very small set of domains and domain arrangements: gene duplicates provide the raw material for adaptive transitions (for example from one fold to another) which are very rare, albeit not impossible. ‘New’ proteins predominantly arise via tinkering, that is by their underlying genes recruiting and adapting smaller fragments of neighbouring DNA or by modular rearrangements of established domain combinations. Such rearrangements arise predominantly via fusion and terminal loss.