RecJ exonuclease plays crucial roles in several DNA repair and recombination pathways, and its ubiquity in bacterial species points to its ancient origin and vital cellular function. RecJ exonuclease from Haemophilus influenzae is a 575-amino-acid protein that harbors the characteristic motifs conserved among RecJ homologs. The purified protein exhibits a processive 5'-3' single-stranded-DNA-specific exonuclease activity. The exonuclease activity of H. influenzae RecJ (HiRecJ) was supported by Mg(2+) or Mn(2+) and inhibited by Cd(2+), suggesting a different mode of metal binding in HiRecJ as compared to Escherichia coli RecJ (EcoRecJ). Site-directed mutagenesis of highly conserved residues in HiRecJ abolished enzymatic activity. Interestingly, substitution of alanine for aspartate 77 resulted in a catalytically inactive enzyme that bound to DNA with a significantly higher affinity as compared to the wild-type enzyme. Noticeably, steady-state kinetic studies showed that H. influenzae single-stranded DNA-binding protein (HiSSB) increased the affinity of HiRecJ for single-stranded DNA and stimulated its exonuclease activity. HiSSB, whose C-terminal tail had been deleted, failed to enhance RecJ exonuclease activity. More importantly, HiRecJ was found to directly associate with its cognate single-stranded DNA-binding protein (SSB), as demonstrated by various in vitro assays. Interaction studies carried out with the truncated variants of HiRecJ and HiSSB revealed that the two proteins interact via the C-terminus of SSB protein and the core-catalytic domain of RecJ. Taken together, these results emphasize direct interaction between RecJ and SSB, which confers functional cooperativity to these two proteins. In addition, these results implicate SSB as being involved in the recruitment of RecJ to DNA and provide insights into the interplay between these proteins in repair and recombination pathways.