Alkaline exonuclease and single-strand DNA (ssDNA) annealing proteins (SSAPs) are key components of DNA recombination and repair systems within many prokaryotes, bacteriophages and virus-like genetic elements. The recently sequenced β-proteobacterium Laribacter hongkongensis (strain HLHK9) encodes putative homologs of alkaline exonuclease (LHK-Exo) and SSAP (LHK-Bet) proteins on its 3.17 Mb genome. Here, we report the biophysical, biochemical and structural characterization of recombinant LHK-Exo protein. LHK-Exo digests linear double-stranded DNA molecules from their 5′-termini in a highly processive manner. Exonuclease activities are optimum at pH 8.2 and essentially require Mg2+ or Mn2+ ions. 5′-phosphorylated DNA substrates are preferred over dephosphorylated ones. The crystal structure of LHK-Exo was resolved to 1.9 Å, revealing a ‘doughnut-shaped’ toroidal trimeric arrangement with a central tapered channel, analogous to that of λ-exonuclease (Exo) from bacteriophage-λ. Active sites containing two bound Mg2+ ions on each of the three monomers were located in clefts exposed to this central channel. Crystal structures of LHK-Exo in complex with dAMP and ssDNA were determined to elucidate the structural basis for substrate recognition and binding. Through structure-guided mutational analysis, we discuss the roles played by various active site residues. A conserved two metal ion catalytic mechanism is proposed for this class of alkaline exonucleases.