Routine manipulation of cellular genomes is contingent upon the development of proteins and enzymes with programmable DNA sequence specificity. Here we describe the structure-guided reprogramming of the DNA sequence specificity of the invertase Gin from bacteriophage Mu and Tn3 resolvase from Escherichia coli. Structure-guided and comparative sequence analyses were used to predict a network of amino acid residues that mediate resolvase and invertase DNA sequence specificity. Using saturation mutagenesis and iterative rounds of positive antibiotic selection, we identified extensively redesigned and highly convergent resolvase and invertase populations in the context of engineered zinc-finger recombinase (ZFR) fusion proteins. Reprogrammed variants selectively catalyzed recombination of nonnative DNA sequences > 10,000-fold more effectively than their parental enzymes. Alanine-scanning mutagenesis revealed the molecular basis of resolvase and invertase DNA sequence specificity. When used as rationally designed ZFR heterodimers, the reprogrammed enzyme variants site-specifically modified unnatural and asymmetric DNA sequences. Early studies on the directed evolution of serine recombinase DNA sequence specificity produced enzymes with relaxed substrate specificity as a result of randomly incorporated mutations. In the current study, we focused our mutagenesis exclusively on DNA determinants, leading to redesigned enzymes that remained highly specific and directed transgene integration into the human genome with > 80% accuracy. These results demonstrate that unique resolvase and invertase derivatives can be developed to site-specifically modify the human genome in the context of zinc-finger recombinase fusion proteins.