ATR-X (alpha-thalassemia/mental retardation, X-linked) syndrome is a human congenital disorder that causes severe intellectual disabilities. Mutations in the ATRX gene, which encodes an ATP-dependent chromatin-remodeler, are responsible for the syndrome. Approximately 50% of the missense mutations in affected persons are clustered in a cysteine-rich domain termed ADD (ATRX-DNMT3-DNMT3L, ADD(ATRX)), whose function has remained elusive. Here we identify ADD(ATRX) as a previously unknown histone H3-binding module, whose binding is promoted by lysine 9 trimethylation (H3K9me3) but inhibited by lysine 4 trimethylation (H3K4me3). The cocrystal structure of ADD(ATRX) bound to H3(1-15)K9me3 peptide reveals an atypical composite H3K9me3-binding pocket, which is distinct from the conventional trimethyllysine-binding aromatic cage. Notably, H3K9me3-pocket mutants and ATR-X syndrome mutants are defective in both H3K9me3 binding and localization at pericentromeric heterochromatin; thus, we have discovered a unique histone-recognition mechanism underlying the ATR-X etiology.