Lactase persistence (LP), the dominant Mendelian trait conferring the ability to digest the milk sugar lactose in adults, has risen to high frequency in central and northern Europeans in the last 20,000 years. This trait is likely to have conferred a selective advantage in individuals who consume appreciable amounts of unfermented milk. Some have argued for the "culture-historical hypothesis," whereby LP alleles were rare until the advent of dairying early in the Neolithic but then rose rapidly in frequency under natural selection. Others favor the "reverse cause hypothesis," whereby dairying was adopted in populations with preadaptive high LP allele frequencies. Analysis based on the conservation of lactase gene haplotypes indicates a recent origin and high selection coefficients for LP, although it has not been possible to say whether early Neolithic European populations were lactase persistent at appreciable frequencies. We developed a stepwise strategy for obtaining reliable nuclear ancient DNA from ancient skeletons, based on (i) the selection of skeletons from archaeological sites that showed excellent biomolecular preservation, (ii) obtaining highly reproducible human mitochondrial DNA sequences, and (iii) reliable short tandem repeat (STR) genotypes from the same specimens. By applying this experimental strategy, we have obtained high-confidence LP-associated genotypes from eight Neolithic and one Mesolithic human remains, using a range of strict criteria for ancient DNA work. We did not observe the allele most commonly associated with LP in Europeans, thus providing evidence for the culture-historical hypothesis, and indicating that LP was rare in early European farmers.