We report a set of radiocarbon dating of prehistoric settlements located on the paleolake Baruun Khuree shores in the Gobi-Altai area, southern Mongolia. The obtained series of 11 AMS 14C measurements on charcoal and other charred plant macro-remains can be associated with one of the earliest episodes of the Holocene highly mobile desert-adapted hunter-gatherers activities from the Gobi desert (ca. 11,250–10,500 cal BP). Exploiting a wide range of environments, including dune fields, they are characterized by pottery usage and microblade core technology with wedge-shaped cores as well as osteological materials. These preliminary results are part of a project analyzing the nature of long-lasting prehistoric occupation around Tsakhiurtyn Hundi (Eng. Flint Valley)—one of the most extensive early prehistoric sites of Central Asia owing its name to the presence of abundant flint outcrops, lithic workshops and their innumerable flint artifacts.