Apurinic/apyrimidinic (AP) endonucleases are key enzymes responsible for the repair of base-less nucleotides generated by spontaneous hydrolysis or as DNA repair intermediates. APE1, the major human AP endonuclease, is a druggable target in cancer and its biological function has been extensively studied. However, the molecular features responsible for its substrate specificity are poorly understood. We show here that, in contrast to APE1, its Arabidopsis ortholog ARP (apurinic endonuclease-redox protein) exhibits orphan base-dependent activity on double-stranded DNA and very poor AP cleavage capacity on single-stranded DNA (ssDNA). We found that these differences are largely a consequence of the variation at two DNA intercalating amino acids that have undergone divergent changes in the metazoan and plant lineages. Swapping the identity of the residue invading the minor groove is sufficient to switch the orphan base specificities of APE1 and ARP. The affinity for ssDNA is largely determined by the major groove invading residue, and swapping its identity switches the ability of APE1 and ARP to cleave AP sites in ssDNA. Importantly, we show that the critical residue for ssDNA cleavage is crucial for mammalian APE1 function in antibody class switch recombination, suggesting an evolutionary advantage for ssDNA activity. These findings provide new molecular insights into the evolution of AP endonucleases.