Recent studies have demonstrated the importance of dynamic heterochromatin-like regions in bacterial gene regulation, particularly for adaptation to changing environments. Here, we have measured the dynamic regulatory protein-DNA landscape of the tuberculosis vaccine strain, BCG Pasteur, under the pathogenically-relevant condition of iron starvation. Our results capture for the first time the overall protein occupancy landscape of the genome of BCG, identifying extended protein occupancy domains likely composed of diverse sets of nucleoid-associated proteins and transcription factors. Importantly, we find chromatin-directed regulation of stress-responsive genes like siderophores. Furthermore, through comparison with the free-living , we identified a specific class of extended protein occupancy domains that are associated with conserved genomic regions across the two organisms, whereas regions with low protein occupancy often lack conservation. Our findings thus comprehensively reveal the contributions of both local regulators and chromatin structure to gene regulation and evolution in mycobacteria.