Epigenome-wide association studies (EWAS) hold promise for the detection of new regulatory mechanisms that may be susceptible to modification by environmental and lifestyle factors affecting susceptibility to disease. Epigenome-wide screening methods cover an increasing number of CpG sites, but the complexity of the data poses a challenge to separating robust signals from noise. Appropriate study design, a detailed a priori analysis plan and validation of results are essential to minimize the danger of false positive results and contribute to a unified approach. Epigenome-wide mapping studies in homogenous cell populations will inform our understanding of normal variation in the methylome that is not associated with disease or aging. Here we review concepts for conducting a stringent and powerful EWAS, including the choice of analyzed tissue, sources of variability and systematic biases, outline analytical solutions to EWAS-specific problems and highlight caveats in interpretation of data generated from samples with cellular heterogeneity.