ABSTRACT Background Tyrosine recombinases perform site-specific genetic recombination in bacteria and archaea. They safeguard genome integrity by resolving chromosome multimers, as well as mobilize transposons, phages and integrons, driving dissemination of genetic traits and antibiotic resistance. Despite their abundance and genetic impact, tyrosine recombinase diversity and evolution has not been thoroughly characterized, which greatly hampers their functional classification. Results Here, we conducted a comprehensive search and comparative analysis of diverse tyrosine recombinases from bacterial, archaeal and phage genomes. We characterized their major phylogenetic groups and show that recombinases of integrons and insertion sequences are closely related to the chromosomal Xer proteins, while integrases of integrative and conjugative elements (ICEs) and phages are more distant. We find that proteins in distinct phylogenetic groups share specific structural features and have characteristic taxonomic distribution. We further trace tyrosine recombinase evolution and propose that phage and ICE integrases originated by acquisition of an N-terminal arm-binding domain. Based on this phylogeny, we classify numerous known ICEs and predict new ones. Conclusions This work provides a new resource for comparative analysis and functional annotation of tyrosine recombinases. We reconstitute protein evolution and show that adaptation for a role in gene transfer involved acquisition of a specific protein domain, which allows precise regulation of excision and integration.