Escherichia coli Exonuclease I (ExoI) digests single-stranded DNA (ssDNA) in the 3'-5' direction in a highly processive manner. The crystal structure of ExoI, determined previously in the absence of DNA, revealed a C-shaped molecule with three domains that form a central positively charged groove. The active site is at the bottom of the groove, while an extended loop, proposed to encircle the DNA, crosses over the groove. Here, we present crystal structures of ExoI in complex with four different ssDNA substrates. The structures all have the ssDNA bound in essentially the predicted manner, with the 3'-end in the active site and the downstream end under the crossover loop. The central nucleotides of the DNA form a prominent bulge that contacts the SH3-like domain, while the nucleotides at the downstream end of the DNA form extensive interactions with an 'anchor' site. Seven of the complexes are similar to one another, but one has the ssDNA bound in a distinct conformation. The highest-resolution structure, determined at 1.95 Å, reveals an Mg(2+) ion bound to the scissile phosphate in a position corresponding to Mg(B) in related two-metal nucleases. The structures provide new insights into the mechanism of processive digestion that will be discussed.