The recJ gene, identified in Escherichia coli, encodes a Mg+2-dependent 5'-to-3' exonuclease with high specificity for single-strand DNA. Genetic and biochemical experiments implicate Red exonuclease tn homologous recombination, base excision, and methyl-directed mismatch repair. Genes encoding proteins with strong similarities to Red have been found in every eubacterial genome sequenced to date, with the exception of Mycoplasma and Mycobacterium tuberculosis. Multiple genes encoding proteins similar to Red are found in some eubacteria, including Bacillus and Helicobacter, and in the archaea, Among this divergent set. of sequences, seven conserved motifs emerge. We demonstrate here that amino acids within six of these moths are essential for both the biochemical and genetic functions off; coli Red, These motifs may define interactions with Mg2+ ions or substrate DNA. A large family of proteins more distantly related to Red is present in archaea, eubacteria, and eukaryotes, including a hypothetical protein in the MgPa adhesin operon of Mycoplasma, a domain of putative polyA polymerases in Synechocystis and Aquifex PRUNE of Drosophila, and an exopolyphosphatase (PPX1) of Saccharomyces cereviseae. Because these six Red motifs are shared between exonucleases and exopolyphosphatases, they may constitute an ancient phosphoesterase domain now found in all kingdoms of life.