The RepK protein, which is encoded by the rolling-circle plasmid pKYM, binds to the PR I site in the pKYM DNA replication origin. We have identified HU as a protein that binds to the PR II and PR III sites in the replication-enhancing region which is downstream of PR I. DNA footprinting assays show that HU binds to these two sites only when RepK is bound to PR I, and that HU also enhances the binding of RepK to PR I. In vivo, pKYM was unable to transform an HU null strain. Two mutant RepK proteins, RepKW179Y, which contains a Trp-to-Tyr exchange at position 179, and RepKD277L, which contains an Asp-to-Leu mutation at residue 277, initiate DNA replication in vivo in the absence of HU. In vitro, these mutant RepK proteins form more stable complexes with the pKYM origin region than does the wild-type RepK protein. These results indicate that HU plays a role in the formation of a stable RepK-origin complex, which is required for the initiation of pKYM DNA replication.