The INK4/ARF locus regulates senescence and is frequently altered in cancer. In normal cells, the INK4/ARF locus is found silenced by Polycomb repressive complexes (PRCs). Which are the mechanisms responsible for the recruitment of PRCs to INK4/ARF and their other target genes remains unclear. In a genetic screen for transcription factors regulating senescence, we identified the homeodomain-containing protein HLX1 (H2.0-like homeobox 1). Expression of HLX1 extends cellular lifespan and blunts oncogene-induced senescence. Using quantitative proteomics, we identified p16 INK4a as the key target mediating the effects of HLX1 in senescence. HLX1 represses p16 INK4a transcription by recruiting PRCs and HDAC1. This mechanism has broader implications, as HLX1 also regulates a subset of PRC targets besides p16 INK4a. Finally, sampling members of the Homeobox family, we identified multiple genes with ability to repress p16 INK4a. Among them, we found HOXA9 (Homeobox A9), a putative oncogene in leukaemia, which also recruits PRCs and HDAC1 to regulate p16 INK4a. Our results reveal an unexpected and conserved interplay between homeodomain-containing proteins and PRCs with implications in senescence, development and cancer.