Polyadenylation of mRNAs in poxviruses, crucial for virion maturation, is carried out by a poly(A) polymerase heterodimer composed of a catalytic component, VP55, and a processivity factor, VP39. The ATP-gamma-S bound and unbound crystal structures of the vaccinia polymerase reveal an unusual architecture for VP55 that comprises of N-terminal, central or catalytic, and C-terminal domains with different topologies and that differs from many polymerases, including the eukaryotic poly(A) polymerases. Residues in the active site of VP55, located between the catalytic and C-terminal domains, make specific interactions with the adenine of the ATP analog, establishing the molecular basis of ATP recognition. VP55's concave surface docks the globular VP39. A model for RNA primer binding that involves all three VP55 domains and VP39 is proposed. The model supports biochemical evidence that VP39 functions as a processivity factor by partially enclosing the RNA primer at the heterodimer interface.