1899年6月24日，在一個紫丁香開放的季節裏，赫定再次朝亞洲的心髒——中國新疆做第四次的探險旅行。這次探險的經費主要是瑞典國王奧斯卡和炸藥大王諾貝爾讚助的。沙皇也對這次旅行給予了支持和幫助，並派了四位哥薩克士兵供他差遣。
在俄屬突厥斯坦的安狄山，赫定和來迎接他的伊斯蘭會合了。伊斯蘭穿的一件長袍上掛滿了國王頒贈的金質勳章。兩人緊緊擁抱在一起，為再一次的曆險舉杯祝福。
7月31日，一切準備就緒，他們帶著新組建的旅行隊——7個人、27匹馬和2隻出生才一個月的小狗（一隻是尤達西的兒子，這條狗和它的父親一樣，也取名叫尤達西；另一隻叫多夫雷）開始朝喀什出發。要去喀什，得長途跋涉430千米的山路，並且翻越鹹海與羅布泊的分水嶺唐布倫山口，此行非常艱險。
他們的目的地是廣闊的亞細亞沙漠，那一片未知的荒漠地區，是探險家們的樂園。赫定預備花三年的時間來完成這一計劃，當然主要的目標是調查一些還未有人涉足過的沙漠。事實上，赫定後來在旅途中繪製的1149張地圖中，其中大部分都從未有人進入過。
在喀什，赫定無意間碰到了他的老友——俄國領事佩德羅夫斯基。佩德羅夫斯基聽說赫定要再次探險，立刻幫他張羅旅行用品。
9月5日下午，旅行隊頂著烈日出發了。在大草原和荒原上走了6天後，他們抵達位於葉爾羌河畔的萊立克。在這裏他們買了一條駁船，又造了一艘小船，一行人搭船順塔裏木河而下，赫定沿途繪了不少精細的河流地圖。
旅行隊順著塔裏木河逐漸深入至沙漠的心髒地帶。
12月7日是這次水上旅程的最後一天。旅隊已經在新湖安營等候。以後的半年間，就以新湖作為根據地，赫定進行了幾次短途旅行。