Cytosolic 5'(3')-deoxyribonucleotidase (cdN) and mitochondrial 5'(3')-deoxyribonucleotidase (mdN) catalyze the dephosphorylation of deoxyribonucleoside monophosphates and regulate dTTP formation in cytosol and mitochondria, protecting DNA replication from imbalanced precursor pools. They can also interfere with the phosphorylation-dependent activation of nucleoside analogues used in anticancer and antiviral treatment. To understand the relatively narrow substrate specificity of these two enzymes and their ability to use nucleotide analogues as substrates, we determined the crystal structures of human cdN in complex with deoxyuridine, murine cdN in complex with dUMP and dGMP, and human mdN in complex with the nucleotide analogues AZTMP and BVdUMP. Our results show that the active site residues Leu45 and Tyr65 in cdN form a more favorable binding surface for purine nucleotides than the corresponding Trp75 and Trp76 in mdN, explaining why cdN has higher activity for purine nucleotides than does mdN. The molecular interactions of mdN with AZTMP and BVdUMP indicate why these nucleotide analogues are poorer substrates as compared with the physiological substrate, and they provide a structural rationale for the design of drugs that are less prone to inactivation by the deoxyribonucleotidases. We suggest that introduction of substituents in the 3'-position may result in nucleoside analogues with increased resistance to dephosphorylation.