Significance How proteins evolved to recognize and bind their ligands is a key mystery in protein function evolution. To explore this mystery, we study how proteins bind adenine, an ancient fragment. We characterize physicochemical patterns of protein–adenine interactions and link these to proteins’ evolutionary origins. In conflict with previous findings, we see that all of adenine’s hydrogen donors and acceptors have been used to bind proteins, and that adenine binding is likely to have emerged multiple times in evolution. To identify adenine-binding sites of shared origin, we use “themes”: short amino acid segments suggested to constitute evolutionary building blocks. We detect specific themes that are engaged in adenine binding; the detection of these in a protein’s sequence might reveal its function.