Because the p16 locus is involved consistently in chromosomal losses found in malignant gastrointestinal stromal tumors (GISTs), we studied p16 in a series of 21 GISTs with complete follow-up using immunohistochemical analysis, semiquantitative reverse transcriptase–polymerase chain reaction (RT-PCR) and methylation-specific PCR (MSP). A fraction of cells of more than 20% with low or absent p16 immunostaining was detected in 12 GISTs, including all showing malignancy. RT-PCR revealed decreased p16 transcription in all except 2 p16 protein–deficient GISTs. By MSP, 7 cases showed p16 promoter methylation (all hypoexpressing p16; 6 malignant). A fraction of p16-deficient cells of more than 20% was associated with clinical malignancy (P = .003; log-rank test). The percentage of cells underexpressing p16, size, cellularity, mitotic count, and coagulative necrosis were associated with malignancy by Cox proportional hazards univariate analysis; only the former factor was selected by multivariate analysis (P = .039). Thus, p16 down-regulation, partly due to p16 promoter methylation, is implied in GIST progression. Furthermore, p16 immunohistochemical assessment seems a promising method for GIST prognostication.