Posttranslational modifications (PTMs) play critical roles in regulating protein functions and mediating protein-protein interactions. An important PTM is lysine methylation that orchestrates chromatin modifications and regulates functions of non-histone proteins. Methyllysine peptides are bound by modular domains, of which chromodomains are representative. Here, we conducted the first large-scale study of chromodomains in the human proteome interacting with both histone and non-histone methyllysine peptides. We observed significant degenerate binding between chromodomains and histone peptides, i.e., different histone sites can be recognized by the same set of chromodomains, and different chromodomains can share similar binding profiles to individual histone sites. Such degenerate binding is not dictated by amino acid sequence or PTM motif but rather rooted in the physiochemical properties defined by the PTMs on the histone peptides. This molecular mechanism is confirmed by the accurate prediction of the binding specificity using a computational model that captures the structural and energetic patterns of the domain-peptide interaction. To further illustrate the power and accuracy of our model, we used it to effectively engineer an exceptionally strong H3K9me3-binding chromodomain and to label H3K9me3 in live cells. This study presents a systematic approach to deciphering domain-peptide recognition and reveals a general principle by which histone modifications are interpreted by reader proteins, leading to dynamic regulation of gene expression and other biological processes.