A major determinant of Vibrio cholerae pathogenicity, the cholera enterotoxin, is encoded in the genome of an integrated phage, CTXvarphi. CTXvarphi integration depends on two host-encoded tyrosine recombinases, XerC and XerD. It occurs at dif1, a 28 bp site on V. cholerae chromosome 1 normally used by XerCD for chromosome dimer resolution. The replicative form of the phage contains two pairs of binding sites for XerC and XerD in inverted orientations. Here we show that in the single-stranded genome of the phage, these sites fold into a hairpin structure, which creates a recombination target for XerCD. In the presence of XerD, XerC can catalyze a single pair of strand exchanges between this target and dif1, resulting in integration of the phage. This integration strategy explains why the rules that normally apply to tyrosine recombinase reactions seemed not to apply to CTXvarphi integration and, in particular, why integration is irreversible.