The toxicity of nucleoside analogs used for the treatment of human immunodeficiency virus infection is due primarily to the inhibition of replication of the mitochondrial genome by the human mitochondrial DNA polymerase (Pol gamma). The severity of clinically observed toxicity correlates with the kinetics of incorporation versus excision of each analog as quantified by a toxicity index, spanning over six orders of magnitude. Here we show that the rate of excision of dideoxycytidine (zalcitabine; ddC) was reduced fourfold (giving a half-life of approximately 2.4 h) by the addition of a physiological concentration of deoxynucleoside triphosphates (dNTPs) due to the formation of a tight ternary enzyme-DNA-dNTP complex at the polymerase site. In addition, we provide a more accurate measurement of the rate of excision and show that the low rate of removal of ddCMP results from both the unfavorable transfer of the primer strand from the polymerase to the exonuclease site and the inefficient binding and/or hydrolysis at the exonuclease site. The analogs ddC, stavudine, and ddATP (a metabolite of didanosine) each bind more tightly at the polymerase site during incorporation than normal nucleotides, and this tight binding contributes to slower excision by the proofreading exonuclease, leading to increased toxicity toward mitochondrial DNA.