In many dsDNA viruses, a single-strand-annealing homologous recombination (SSA) reaction is catalyzed by a pair of proteins. In phage lambda, this system is called Red, and is composed of lambda exonuclease (Lambda-Exo, a 5' to 3' dsDNA exonuclease), and Red-Beta (a ssDNA binding protein and annealase). I examined the physical and mechanistic coupling of Lambda-Exo and Red-Beta and confirmed that these proteins form a complex with a 1:1 subunit stoichiometry. The size of this complex was shown to be close to one MDa, possibly composed of 12 Lambda-Exo and 12 Red-Beta monomers. Red-Beta decreased the extent of digestion of dsDNA by Lambda-Exo, possibly by preventing its rebinding. The processivity of Lambda-Exo was not affected by Red-Beta, but the dwell-time of Lambda-Exo was significantly increased by Red-Beta. These effects of Red-Beta on Lambda-Exo may have important roles in controlling the SSA reaction by preventing hyper-resection of DNA, and/or by stabilizing Lambda-Exo/DNA complexes. The previous observations that Red-Beta protects ssDNA from nucleases and that SSB inhibits Red-Beta assembly onto ssDNA were confirmed and strengthened by our results. We determined that Red-Beta inhibits SSB binding to nascent ssDNA generated by Lambda-Exo. This strongly suggests that generation of nascent ssDNA by Lambda-Exo is coupled to assembly of Red-Beta onto nascent ssDNA. We describe two models for this coupled assembly: Model One suggests that Lambda-Exo loads Red-Beta on nascent ssDNA providing a kinetic advantage over SSB, and Model Two proposes that the complex of Lambda-Exo and Red-Beta feeds ssDNA directly onto the dodecameric Red-Beta ring. It was suggested that Lambda-Exo forms a topological link with nascent ssDNA, thereby making digestion highly processive. We challenged this model by removing the nascent ssDNA with ExoI during a Lambda-Exo digestion reaction. We observed that the nascent ssDNA was a major contributor to the processivity of Lambda-Exo since removal of nascent ssDNA resulted in a drastic decrease in the processivity of Lambda-Exo. This is the first demonstration that DNA is a processivity factor, strengthening the view that processive DNA processing enzymes should be thought of as nucleoprotein complexes that must be kinetically treated as both substrate and enzyme.