It is known that the initiation of bacteriophage lambda replication requires the orderly assembly of the lambda O.lambda P.DnaB helicase protein preprimosomal complex at the ori lambda DNA site. The DnaK, DnaJ, and GrpE heat shock proteins act together to destabilize the lambda P.DnaB complex, thus freeing DnaB and allowing it to unwind lambda DNA near the ori lambda site. The first step of this disassembly reaction is the binding of DnaK to the lambda P protein. In this report, we examined the influence of the DnaJ and GrpE proteins on the stability of the lambda P.DnaK complex. We present evidence for the existence of the following protein-protein complexes: lambda P.DnaK, lambda P.DnaJ, DnaJ.DnaK, DnaK.GrpE, and lambda P.DnaK.GrpE. Our results suggest that the presence of GrpE alone destabilizes the lambda P.DnaK complex, whereas the presence of DnaJ alone stabilizes the lambda P.DnaK complex. Using immunoprecipitation, we show that in the presence of GrpE, DnaK exhibits a higher affinity for the lambda P.DnaJ complex than it does alone. Using cross-linking with glutaraldehyde, we show that oligomeric forms of DnaK exhibit a higher affinity for lambda P than monomeric DnaK. However, in the presence of GrpE, monomeric DnaK can efficiently bind lambda P protein. These findings help explain our previous results, namely that in the GrpE-dependent lambda DNA replication system, the DnaK protein requirement can be reduced up to 10-fold.