Abnormal DNA methylation is observed in certain promoters of neoplastic cells, although the likelihood of methylation for each individual promoter varies. Simultaneous analysis of many promoters in the same sample can allow use of statistical methods for identification of neoplasia. Here we describe an assay for such analysis, based on digestion of genomic DNA with methylation-sensitive restriction enzyme and multiplexed PCR with gene-specific primers (MSRE-PCR). MSRE-PCR includes extensive digestion of genomic DNA (uncut fragments cannot be identified by PCR), can be applied to dilute samples (<1 pg/microl), requires limited amount of starting material (42 pg or genomic equivalent of seven cells) and can identify methylation in a heterogeneous mix containing <2% of cells with methylated fragments. When applied to 53 promoters of breast cancer cell lines MCF-7, MDA-MB-231 and T47D, MSRE-PCR correctly identified the methylation status of genes analyzed by other techniques. For selected genes results of MSRE-PCR were confirmed by methylation-specific PCR and bisulfite sequencing. The assay can be configured for any number of desired targets in any user-defined set of genes.