It has been established that East Asian summer monsoon intensity varies with Dansgaard-Oeschger cycles, suggesting a connection between the climates of East Asia and the North Atlantic on a millennial timescale. However, the dynamics of such a connection are still unsolved. Here we demonstrate that temporal changes in the provenance of aeolian dust in Japan Sea sediments, which we interpret to reflect changes in the westerly jet path over East Asia, exhibit variations in harmony with Dansgaard-Oeschger cycles. The dominance of dust with a Mongolian Gobi provenance during stadials suggests a westerly jet axis located to the south of the Himalaya-Tibetan Plateau throughout most of the year, whereas the co-dominance of dust from both the Taklimakan Desert and the Mongolian Gobi during interstadials suggests that the westerly jet axis jumped to the north of the Tibetan Plateau at latest in summer. As the shift of the westerly jet axis to the north of the Tibetan Plateau is closely related to the onset of the East Asian summer monsoon, changes of the westerly jet path apparently critically affect the teleconnection between the climates of Asia and North Atlantic on a millennial timescale.