Biological responses to histone methylation critically depend on the faithful readout and transduction of the methyl-lysine signal by "effector" proteins, yet our understanding of methyl-lysine recognition has so far been limited to the study of histone binding by chromodomain and WD40-repeat proteins. The double tudor domain of JMJD2A, a Jmjc domain-containing histone demethylase, binds methylated histone H3-K4 and H4-K20. We found that the double tudor domain has an interdigitated structure, and the unusual fold is required for its ability to bind methylated histone tails. The cocrystal structure of the JMJD2A double tudor domain with a trimethylated H3-K4 peptide reveals that the trimethyl-K4 is bound in a cage of three aromatic residues, two of which are from the tudor-2 motif, whereas the binding specificity is determined by side-chain interactions involving amino acids from the tudor-1 motif. Our study provides mechanistic insights into recognition of methylated histone tails by tudor domains and reveals the structural intricacy of methyl-lysine recognition by two closely spaced effector domains.