Uracil-DNA glycosylase (UDG) is a key repair enzyme responsible for removing uracil residues from DNA. Interestingly, UDG is the only enzyme known to be inhibited by two different DNA mimic proteins: p56 encoded by the Bacillus subtilis phage 29 and the well-characterized protein Ugi encoded by the B. subtilis phage PBS1/PBS2. Atomic-resolution crystal structures of the B. subtilis UDG both free and in complex with p56, combined with site-directed mutagenesis analysis, allowed us to identify the key amino acid residues required for enzyme activity, DNA binding and complex formation. An important requirement for complex formation is the recognition carried out by p56 of the protruding Phe191 residue from B. subtilis UDG, whose side-chain is inserted into the DNA minor groove to replace the flipped-out uracil. A comparative analysis of both p56 and Ugi inhibitors enabled us to identify their common and distinctive features. Thereby, our results provide an insight into how two DNA mimic proteins with different structural and biochemical properties are able to specifically block the DNA-binding domain of the same enzyme.