We have found, using a newly developed genetic method, a protein (named Cnu, for oriC-binding nucleoid-associated) that binds to a specific 26-base-pair sequence (named cnb) in the origin of replication of Escherichia coli, oriC. Cnu is composed of 71 amino acids (8.4 kDa) and shows extensive amino acid identity to a group of proteins belonging to the Hha/YmoA family. Cnu was previously discovered as a protein that, like Hha, complexes with H-NS in vitro. Our in vivo and in vitro assays confirm the results and further suggest that the complex formation with H-NS is involved in Cnu/Hha binding to cnb. Unlike the hns mutants, elimination of either the cnu or hha gene did not disturb the growth rate, origin content, and synchrony of DNA replication initiation of the mutants compared to the wild-type cells. However, the cnu hha double mutant was moderately reduced in origin content. The Cnu/Hha complex with H-NS thus could play a role in optimal activity of oriC.