Aberrant methylation of CpG islands is an important pathway for regulation of gene expression. Recent data suggest that epigenetic abnormalities may occur very early in lung carcinogenesis. We studied the promoters of the four genes, HOX A9, p16(INK4a) (p16), MAGE A1 and MAGE B2 by methylation-specific PCR in matched normal tissue, tumour, and cytological negative sputum samples obtained from 22 patients with non-small cell lung cancer (NSCLC). We further report methylation abnormalities in sputum samples from 56 smokers with differential cytology readouts (negative, inflammatory changes, suspicious, and cancer). Our method was successfully performed on formalin-fixed and paraffin-embedded (FFPE) samples, and was fit to study only few cells obtained by a convenient non-invasive sputum collection and handling. The promoters of MAGE A1 and MAGE B2 had abnormal methylation patterns in, respectively, 50% and 41% of the cytologically negative sputum samples from NSCLC patients, whereas methylation abnormalities of p16 was observed in 27% of negative sputum samples. Interestingly, 95.5% (21 of 22) of the cytologically negative sputum samples from NSCLC patients had abnormal methylation in at least one of the four genes indicating a high sensitivity of this marker system. Moreover, a higher frequency of methylation abnormalities was observed in sputum samples from smokers with high cytological grade compared to low cytological grade. We conclude that the identification of abnormal gene methylation of a limited number of markers in FFPE sputum samples is feasible and may be investigated as a potential system for population-based screening of early stages of lung cancer.