Aberrant hypo-methylation of DNA is evident in a range of human diseases including cancer and diabetes. Development of sensitive assays capable of detecting traces of un-methylated DNA within methylated samples can be useful in several situations. Here we describe a new approach, fast-COLD-MS-PCR, which amplifies preferentially un-methylated DNA sequences. By employing an appropriate denaturation temperature during PCR of bi-sulfite converted DNA, fast-COLD-MSPCR enriches un-methylated DNA and enables differential melting analysis or bisulfite sequencing. Using methylation on the MGMT gene promoter as a model, it is shown that serial dilutions of controlled methylation samples lead to the reliable sequencing of un-methylated sequences down to 0.05% un-methylated-to-methylated DNA. Screening of clinical glioma tumor and infant blood samples demonstrated that the degree of enrichment of un-methylated over methylated DNA can be modulated by the choice of denaturation temperature, providing a convenient method for analysis of partially methylated DNA or for revealing and sequencing traces of un-methylated DNA. Fast-COLD-MS-PCR can be useful for the detection of loss of methylation/imprinting in cancer, diabetes or diet-related methylation changes.