Exonuclease X (ExoX) is a distributive DnaQ exonuclease that cleaves both ssDNA and dsDNA substrates. Here, we present the crystal structures of Escherichia coli ExoX in complex with three different dsDNA substrates. 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. These results also provide insight into the structural framework of the different substrate specificities of the DnaQ family members.