Histones undergo several different post-translational modifications that control a variety of physiological processes. These covalent modifications show substantial cross-regulation, providing a wealth of regulatory potential. New insights into the communication between modifications on histones have emerged in recent years. This review assesses the current understanding of cross-regulation of histone modifications and identifies future questions to be addressed in this field.