Background: Uracil-DNA glycosylases are evolutionarily conserved DNA repair enzymes. However, vaccinia virus uracil-DNA glycosylase (known as D4), also serves as an intrinsic and essential component of the processive DNA polymerase complex during DNA replication. In this complex D4 binds to a unique poxvirus specific protein A20 which tethers it to the DNA polymerase. At the replication fork the DNA scanning and repair function of D4 is coupled with DNA replication. So far, DNA-binding to D4 has not been structurally characterized. Results: This manuscript describes the first structure of a DNA-complex of a uracil-DNA glycosylase from the poxvirus family. This also represents the first structure of a uracil DNA glycosylase in complex with an undamaged DNA. In the asymmetric unit two D4 subunits bind simultaneously to complementary strands of the DNA double helix. Each D4 subunit interacts mainly with the central region of one strand. DNA binds to the opposite side of the A20-binding surface on D4. Comparison of the present structure with the structure of uracil-containing DNA-bound human uracil-DNA glycosylase suggests that for DNA binding and uracil removal D4 employs a unique set of residues and motifs that are highly conserved within the poxvirus family but different in other organisms. Conclusion: The first structure of D4 bound to a truly non-specific undamaged double-stranded DNA suggests that initial binding of DNA may involve multiple non-specific interactions between the protein and the phosphate backbone.