After the domestication of animals and crops in the Near East some 11,000 years ago, farming had reached much of central Europe by 7500 years before the present. The extent to which these early European farmers were immigrants or descendants of resident hunter-gatherers who had adopted farming has been widely debated. We compared new mitochondrial DNA (mtDNA) sequences from late European hunter-gatherer skeletons with those from early farmers and from modern Europeans. We find large genetic differences between all three groups that cannot be explained by population continuity alone. Most (82%) of the ancient hunter-gatherers share mtDNA types that are relatively rare in central Europeans today. Together, these analyses provide persuasive evidence that the first farmers were not the descendants of local hunter-gatherers but immigrated into central Europe at the onset of the Neolithic.