Members of the DnaQ superfamily are major 3'-5' exonucleases that degrade either only single-stranded DNA (ssDNA) or both ssDNA and double-stranded DNA (dsDNA). However, the mechanism by which dsDNA is recognized and digested remains unclear. Exonuclease X (ExoX) is a distributive DnaQ exonuclease that cleaves both ssDNA and dsDNA substrates. Here, we report the crystal structures of Escherichia coli ExoX in complex with three different dsDNA substrates: 3' overhanging dsDNA, blunt-ended dsDNA and 3' recessed mismatch-containing dsDNA. In these structures, ExoX binds to dsDNA via both a conserved substrate strand-interacting site and a previously uncharacterized complementary strand-interacting motif. When ExoX complexes with blunt-ended dsDNA or 5' overhanging dsDNA, a 'wedge' composed of Leu12 and Gln13 penetrates between the first two base pairs to break the 3' terminal base pair and facilitates precise feeding of the 3' terminus of the substrate strand into the ExoX cleavage active site. Site-directed mutagenesis showed that the complementary strand-binding site and the wedge of ExoX are dsDNA specific. Together with the results of structural comparisons, our data support a mechanism by which normal and mismatched dsDNA are recognized and digested by E. coli ExoX. The crystal structures also provide insight into the structural framework of the different substrate specificities of the DnaQ family members.