We detected tumor-associated aberrant hypermethylation of the p16 gene in plasma DNA from 105 non-small cell lung cancer (NSCLC) patients (65 squamous cell carcinoma (SCC) and 40 adenocarcinoma (ADC)) and 92 matched tumor DNA samples, using a modified semi-nested methylation-specific PCR (MSP). This technique increased the sensibility of detecting p16 hypermethylation from DNA samples in varying stages. p16 hypermethylation was present in 73.3% (77/105) of the plasma samples, and 79.3% (73/92) of the tumor samples. Among those cases with methylated p16 sequence in tumor samples, 87.7% (64/73) also demonstrated this epigenetic alteration in the corresponding plasma DNA. Only patients whose tumor cells had hypermethylated p16 gene exhibited aberrant methylation in their plasma samples. Regarding different clinical stages of SCC and ADC, the frequencies of p16 hypermethylation in plasma DNA were nearly the same as those in corresponding tumors, except for stage I ADC. Our study indicated that aberrant methylation of p16 may be an excellent biomarker for early diagnosis and follow-up of NSCLC patients, and MSP is a reliable method for these purposes.