The type II topoisomerase TopoIV, which has an essential role in Escherichia coli chromosome decatenation, interacts with MukBEF, an SMC (structural maintenance of chromosomes) complex that acts in chromosome segregation. We have characterized the intracellular dynamics of individual TopoIV molecules and the consequences of their interaction with MukBEF clusters by using photoactivated-localization microscopy. We show that ~15 TopoIV molecules per cell are associated with MukBEF clusters that are preferentially localized to the replication origin region (ori), close to the long axis of the cell. A replication-dependent increase in the fraction of immobile molecules, together with a proposed catalytic cycle of ~1.8 s, is consistent with the majority of active TopoIV molecules catalyzing decatenation, with a minority maintaining steady-state DNA supercoiling. Finally, we show that the MukB-ParC interaction is crucial for timely decatenation and segregation of newly replicated ori DNA.