Bacterial nucleoid-associated proteins play important roles in chromosome organization and global gene regulation. We find that Lsr2 of Mycobacterium tuberculosis is a unique nucleoid-associated protein that binds AT-rich regions of the genome, including genomic islands acquired by horizontal gene transfer and regions encoding major virulence factors, such as the ESX secretion systems, the lipid virulence factors PDIM and PGL, and the PE/PPE families of antigenic proteins. Comparison of genome-wide binding data with expression data indicates that Lsr2 binding results in transcriptional repression. Domain-swapping experiments demonstrate that Lsr2 has an N-terminal dimerization domain and a C-terminal DNA-binding domain. Nuclear magnetic resonance analysis of the DNA-binding domain of Lsr2 and its interaction with DNA reveals a unique structure and a unique mechanism that enables Lsr2 to discriminately target AT-rich sequences through interactions with the minor groove of DNA. Taken together, we provide evidence that mycobacteria have employed a structurally distinct molecule with an apparently different DNA recognition mechanism to achieve a function similar to the Enterobacteriaceae H-NS, likely coordinating global gene regulation and virulence in this group of medically important bacteria.