Bacteriophage-encoded single strand annealing proteins (SSAPs) are recombinases which can substitute the classical, bacterial RecA and manage the DNA metabolism at different steps of phage propagation. SSAPs have been shown to efficiently promote recombination between short and rather divergent DNA sequences and were exploited for in vivo genetic engineering mainly in Gram-negative bacteria. In opposition to the conserved and almost universal bacterial RecA protein, SSAPs display great sequence diversity. The importance for SSAPs in phage biology and phage-bacteria evolution is underlined by their role as key players in events of horizontal gene transfer (HGT). All of the above provoke a constant interest for the identification and study of new phage recombinase proteins in vivo , in vitro as well as in silico . Despite this, a huge body of putative ssap genes escapes conventional classification, as they are not properly annotated. In this work, we performed a wide-scale identification, classification and analysis of SSAPs encoded by the Firmicutes bacteria and their phages. By using sequence similarity network and gene context analyses, we created a new high quality dataset of phage-related SSAPs, substantially increasing the number of annotated SSAPs. We classified the identified SSAPs into seven distinct families, namely RecA, Gp2.5, RecT/Redβ, Erf, Rad52/22, Sak3, and Sak4, organized into three superfamilies. Analysis of the relationships between the revealed protein clusters led us to recognize Sak3-like proteins as a new distinct SSAP family. Our analysis showed an irregular phylogenetic distribution of ssap genes among different bacterial phyla and specific phages, which can be explained by the high rates of ssap HGT. We propose that the evolution of phage recombinases could be tightly linked to the dissemination of bacterial phage-resistance mechanisms (e.g., abortive infection and CRISPR/Cas systems) targeting ssap genes and be a part of the constant phage-bacteria arms race.