In monoecious melon (Cucumis melo), sex is determined by the differential expression of sex determination genes (SDGs) and adoption of sex-specific transcriptional programs. Histone modifications such as H3K27me3 have been previously shown to be a hallmark associated to unisexual flower development in melon; yet, no genetic approaches have been conducted for elucidating the roles of H3K27me3 writers, readers, and erasers in this process. Here we show that melon homologs to Arabidopsis LHP1, CmLHP1A and B, redundantly control several aspects of plant development, including sex expression. Cmlhp1ab double mutants displayed an overall loss and redistribution of H3K27me3, leading to a deregulation of genes involved in hormone responses, plant architecture, and flower development. Consequently, double mutants display pleiotropic phenotypes and, interestingly, a general increase of the male:female ratio. We associated this phenomenon with a general deregulation of some hormonal response genes and a local activation of male-promoting SDGs and MADS-box transcription factors. Altogether, these results reveal a novel function for CmLHP1 proteins in maintenance of monoecy and provide novel insights into the polycomb-mediated epigenomic regulation of sex lability in plants.