Epigenetic regulators are multiprotein complexes that modify chromatin architecture to control gene expression in response to developmental and environmental cues. These complexes function in a highly coordinated manner, often collaborating with various accessory proteins to precisely regulate the dynamic nature of chromatin states. However, our understanding of how these core histone-modifying regulators co-evolved with accessory proteins during plant evolution remains limited. Therefore, in this review, we summarize the evolution of major histone modification regulators, with a focus on Polycomb group complexes and their associated accessory proteins. We discuss how accessory proteins have evolved to modulate the activity of conserved core components, supporting key innovations during plant evolution. Lastly, we highlight the role of accessory proteins in mediating crosstalk between histone-modifying complexes, emerging as key evolutionary factors that shape the epigenetic landscape and influence plant development and environmental adaptation.