Ancient genomes have revolutionised our understanding of Holocene prehistory in Western Eurasia, but Asia has received limited attention. Here we report genomic data from two individuals from an early Neolithic site, Devil’s Gate (7742-7638 cal years before present) in East Asia, on the border between Russia and Korea. These hunter-gatherers are genetically most similar to geographically close populations from the Amur Basin, in particular the Ulchi, implying a high level of continuity in this region over most of the Holocene. Japanese and Koreans, who live further south, also showed genetic affinity to Devil’s Gate; both these modern day populations were best described as mixes of a population close to Devil’s Gate, likely the ancestral hunter-gatherers who inhabited that region, and modern populations from southern China and South-East Asia, possibly linked to the onset of the Neolithic around 8,000 years ago in the region. Thus, in contrast to Western Eurasia, East Asia experienced a higher degree of continuity, with little input in the northern regions and an integrations of incoming farmers and local hunter-gatherers further south.