The post-translational modification of histones regulates many cellular processes, including transcription, replication and DNA repair. A large number of combinations of post-translational modifications are possible. This cipher is referred to as the histone code. Many of the enzymes that lay down this code have been identified. However, so far, few code-reading proteins have been identified. Here, we describe a protein-array approach for identifying methyl-specific interacting proteins. We found that not only chromo domains but also tudor and MBT domains bind to methylated peptides from the amino-terminal tails of histones H3 and H4. Binding specificity observed on the protein-domain microarray was corroborated using peptide pull-downs, surface plasma resonance and far western blotting. Thus, our studies expose tudor and MBT domains as new classes of methyl-lysine-binding protein modules, and also demonstrates that protein-domain microarrays are powerful tools for the identification of new domain types that recognize histone modifications.