The topological homeostasis of bacterial chromosomes is maintained by the balance between compaction and the topological organization of genomes. Two classes of proteins play major roles in chromosome organization: the nucleoid-associated proteins (NAPs) and topoisomerases. The NAPs bind DNA to compact the chromosome, whereas topoisomerases catalytically remove or introduce supercoils into the genome. We demonstrate that HU, a major NAP ofMycobacterium tuberculosisspecifically stimulates the DNA relaxation ability of mycobacterial topoisomerase I (TopoI) at lower concentrations but interferes at higher concentrations. A direct physical interaction betweenM. tuberculosisHU (MtHU) and TopoI is necessary for enhancing enzyme activity bothin vitroandin vivo. The interaction is between the amino terminal domain of MtHU and the carboxyl terminal domain of TopoI. Binding of MtHU did not affect the two catalytic trans-esterification steps but enhanced the DNA strand passage, requisite for the completion of DNA relaxation, a new mechanism for the regulation of topoisomerase activity. An interaction-deficient mutant of MtHU was compromised in enhancing the strand passage activity. The species-specific physical and functional cooperation between MtHU and TopoI may be the key to achieve the DNA relaxation levels needed to maintain the optimal superhelical density of mycobacterial genomes.