To maximize spread of their host intron or intein, many homing endonucleases recognize nucleotides that code for important and conserved amino acid residues of the target gene. Here, we examine the cleavage requirements for I-TevI, which binds a stretch of thymidylate synthase (TS) DNA that codes for functionally critical residues in the TS active site. Using an in vitro selection scheme, we identified two base-pairs in the I-TevI cleavage site region as important for cleavage efficiency. These were confirmed by comparison of I-TevI cleavage efficiencies on mutant and on wild-type substrates. We also showed that nicking of the bottom strand by I-TevI is not affected by mutation of residues surrounding the bottom-strand cleavage site, unlike other homing endonucleases. One of these two base-pairs is universally conserved in all TS sequences, and is identical with a previously identified cleavage determinant of I-BmoI, a related GIY-YIG endonuclease that binds a homologous stretch of TS-encoding DNA. The other base-pair is conserved only in a subset of TS genes that includes the I-TevI, but not the I-BmoI, target sequence. Both the I-TevI and I-BmoI cleavage site requirements correspond to functionally critical residues involved in an extensive hydrogen bond network within the TS active site. Remarkably, these cleavage requirements correlate with TS phylogeny in bacteria, suggesting that each endonuclease has individually adapted to efficiently cleave distinct TS substrates.