Evolutionary annotation of genome maintenance (GM) proteins has conventionally been established by remote relationships within protein sequence databases. However, often no significant relationship can be established. Highly sensitive approaches to attain remote homologies based on iterative profile-to-profile methods have been developed. Still, these methods have not been systematically applied in evolutionary annotation of GM proteins. Here, by applying profile-to-profile models, we systematically survey the repertoire of GM proteins from bacteria to man. We identify multiple new GM protein candidates and annotate new domains in numerous established GM proteins, among other PARP, OB-fold, Macro, SAP, BRCT, KU, SANT, and nuclease domains. We experimentally validate OB-fold and MIS18/Yippee domains in SPIDR and in FAM72 protein families, respectively. Our results indicate that, surprisingly, despite the immense interest and long-term research efforts, the full repertoire of genome stability caretakers is still not fully appreciated.