Background The West Liao River valley in Northeast China is an ecologically diverse region, populated in prehistory by human populations with a wide range of cultures and modes of subsistence. To help understand the human evolutionary history of this region, we performed Y chromosome analyses on ancient human remains from archaeological sites ranging in age from 6500 to 2700 BP. Results 47 of the 70 individuals provided reproducible results. They were assigned into five different Y sub-haplogroups using diagnostic single nucleotide polymorphisms, namely N1 (xN1a, N1c), N1c, C/C3e, O3a (O3a3) and O3a3c. We also used 17 Y short tandem repeat loci in the non-recombining portion of the Y chromosome. There appears to be significant genetic differences between populations of the West Liao River valley and adjacent cultural complexes in the prehistoric period, and these prehistoric populations were shown to carry similar haplotypes as present-day Northeast Asians, but at markedly different frequencies. Conclusion Our results suggest that the prehistoric cultural transitions were associated with immigration from the Yellow River valley and the northern steppe into the West Liao River valley. They reveal the temporal continuity of Y chromosome lineages in populations of the West Liao River valley over 5000 years, with a concurrent increase in lineage diversity caused by an influx of immigrants from other populations.