The INK4a/ARF locus encodes the key tumor suppressors p15INK4b, p16INK4a and p19ARF, which prevent propagation of cells with cancerous potential through regulation of cellular senescence. Therefore, it is not surprising that INK4a/ARF is the most frequently inactivated locus in human cancer. P16INK4a, specifically, is lost at high frequency in several cancers, including non-small cell lung carcinoma (NSCLC). While hypermethylation is responsible for p16INK4a loss in nearly half the cases, the mechanism for the remaining cases is unknown. Here, we demonstrate that E6AP is a major inducer of the INK4/ARF locus. We defined an alternative methylation-independent mechanism for the silencing of p16INK4a, involving the E6AP-E2F1-Cdc6 axis. Importantly, in a subset of NSCL, E6AP-low/Cdc6-high/p16INK4a-low expression profile is associated with worse overall survival and a low frequency of p16INK4a hypermethylation, thereby defining a prognostic value for this expression profile in NSCLC.