HD-domain phosphohydrolases have nucleotidase and phosphodiesterase activities and play important roles in the metabolism of nucleotides and in signaling. We present three 2.1-A-resolution crystal structures (one in the free state and two complexed with natural substrates) of an HD-domain phosphohydrolase, the Escherichia coli 5'-nucleotidase YfbR. The free-state structure of YfbR contains a large cavity accommodating the metal-coordinating HD motif (H33, H68, D69, and D137) and other conserved residues (R18, E72, and D77). Alanine scanning mutagenesis confirms that these residues are important for activity. Two structures of the catalytically inactive mutant E72A complexed with Co(2+) and either thymidine-5'-monophosphate or 2'-deoxyriboadenosine-5'-monophosphate disclose the novel binding mode of deoxyribonucleotides in the active site. Residue R18 stabilizes the phosphate on the Co(2+), and residue D77 forms a strong hydrogen bond critical for binding the ribose. The indole side chain of W19 is located close to the 2'-carbon atom of the deoxyribose moiety and is proposed to act as the selectivity switch for deoxyribonucleotide, which is supported by comparison to YfdR, another 5'-nucleotidase in E. coli. The nucleotide bases of both deoxyriboadenosine-5'-monophosphate and thymidine-5'-monophosphate make no specific hydrogen bonds with the protein, explaining the lack of nucleotide base selectivity. The YfbR E72A substrate complex structures also suggest a plausible single-step nucleophilic substitution mechanism. This is the first proposed molecular mechanism for an HD-domain phosphohydrolase based directly on substrate-bound crystal structures.