Holocene environment change in the Gobi Desert of Mongolia and northwestern China is of global significance as it is one of the key dust source areas of the world. The Juyanze Basin, located in the central Gobi Desert of southern Mongolian Plateau, is one of the three terminal basins of the Heihe River that flows north from the Qilian Mountain. A series of geomorphic shorelines at different elevations around the basin indicate that large lake levels fluctuated during the past. In this study, we measured the exact elevation of shorelines in the Juyanze Basin using Digital Global Positioning System and found seven shorelines at ~37, ~36, ~34, ~30, ~28, ~24, and ~22 m above modern basin floor (a.m.b.f.). Optically stimulated luminescence dating was employed to date the deposition of beach sand and gravel sequences at these shorelines. Results indicate a paleolake developed in the basin at ~5 ka when lake levels reached ~26 m a.m.b.f.. The lake level then gradually increased to ~29 m a.m.b.f. at ~3.3 ka and reached its highest Holocene level of~37 m a.m.b.f. at ~2.7 ka. The lake environment during 1.1–0.8 ka was characterized by frequent lake-level fluctuations at ~30 m a.m.b.f. The lake disappeared from both East and West Juyanze Basin after ~0.6 ka. This sequence is out-of-phase with other regional Holocene lake records which indicate Holocene high stands occurred during the early to middle Holocene. We suggest that out-of-phase lake high stands at ~5–1 ka in the Juyanze Basin are related to geomorphological shifts of the Heihe River channels across its fan/delta, feeding the three sub-basins of the Ejina at different times. Using paleolake shorelines in this region to reconstruct the climate changes needs to be very careful.