The vaccinia virus E9 protein, the catalytic subunit of the DNA polymerase holoenzyme, is inherently distributive under physiological conditions, although infected cells contain a highly processive form of the enzyme. The viral A20 protein was previously characterized as a stoichiometric component of the processivity factor, and an interaction between A20 and E9 was documented in vivo. A20 has been shown to interact with D4, the virally encoded uracil DNA glycosylase (UDG), by yeast-two hybrid and in vitro analysis. Here we confirm that UDG and A20 interact in vivo and show that temperature-sensitive viruses with lesions in the D4R gene show a profound defect in DNA synthesis at the non-permissive temperature. Moreover, cytoplasmic extracts prepared from these infections lack processive polymerase activity in vitro, implicating D4 in the assembly or activity of the processive polymerase. Upon overexpression of 3xFLAG-UDG, A20, and E9 in various combinations, we purified dimeric and trimeric UDG-A20 and UDG-A20-polymerase complexes, respectively. These complexes are stable in 750 mm NaCl and can be further purified by Mono Q chromatography. Notably, the trimeric complex displays robust processive polymerase activity, and the dimeric complex can confer processivity on purified E9. Consistent with previous reports that the catalytic activity of UDG is dispensable for virus replication in tissue culture, we find that the role of UDG role in the polymerase complex is not diminished by mutations targeting residues involved in uracil recognition or excision. Our cumulative data support the conclusion that A20 and UDG form a heterodimeric processivity factor that associates with E9 to comprise the processive polymerase holoenzyme.