The SeqA protein, which prevents overinitiation of chromosome replication, has been suggested to also participate in the segregation of chromosomes in Escherichia coli. Using a bacterial two-hybrid system, we found that SeqA interacts with the ParC subunit of topoisomerase IV (topo IV), a type II topoisomerase involved in decatenation of daughter chromosomes and relief of topological constraints generated by replication and transcription. We demonstrated that purified SeqA protein stimulates the activities of topo IV, both in relaxing supercoiled plasmid DNA and converting catenanes to monomers. The same moderate levels of SeqA protein did not affect the activities of DNA gyrase or topoisomerase I. At higher levels of SeqA, topo IV favored the formation of catenanes, caused by intermolecular strand exchange among plasmid DNA aggregates formed by SeqA. Excess SeqA inhibited the activity of all topoisomerases. We also found that stimulation of topo IV was dependent upon the affinity of SeqA for DNA. Our results suggest that this stimulation is mediated by the specific interaction of topo IV with SeqA. Some of the known phenotypes of mutant cells lacking SeqA, such as deficient chromosome segregation and increased negative superhelicity, support that the SeqA protein is required for topo IV-mediated relaxation and decatenation of chromosomes and plasmids, during and after their replication.