Mitochondrial DNA polymerase (pol gamma) is the sole DNA polymerase responsible for replication and repair of animal mitochondrial DNA. Here, we address the molecular mechanism by which the human holoenzyme achieves high processivity in nucleotide polymerization. We have determined the crystal structure of human pol gamma-beta, the accessory subunit that binds with high affinity to the catalytic core, pol gamma-alpha, to stimulate its activity and enhance holoenzyme processivity. We find that human pol gamma-beta shares a high level of structural similarity to class IIa aminoacyl tRNA synthetases, and forms a dimer in the crystal. A human pol gamma/DNA complex model was developed using the structures of the pol gamma-beta dimer and the bacteriophage T7 DNA polymerase ternary complex, which suggests multiple regions of subunit interaction between pol gamma-beta and the human catalytic core that allow it to encircle the newly synthesized double-stranded DNA, and thereby enhance DNA binding affinity and holoenzyme processivity. Biochemical properties of a novel set of human pol gamma-beta mutants are explained by and test the model, and elucidate the role of the accessory subunit as a novel type of processivity factor in stimulating pol gamma activity and in enhancing processivity.