戰勝了乃蠻部之後，成吉思汗每天都很忙碌。善後、防備都是重要的工作。因為在此時，乃蠻的殘餘勢力和札木合率領的札答蘭氏、脫脫率領的蔑兒乞氏，以及朵兒邊、塔塔兒、弘吉剌、合答斤和山只昆等部結成的反成吉思汗聯盟的殘餘勢力仍然存在。原本投靠了乃蠻的阿勒壇和忽察兒下落不明。
他們就像火種一樣潛伏在草原上、森林裡或者山上，不知什麼時候便有可能重新集結到一起，捲土重來。
為了鞏固政權，就要在殘餘勢力最弱的時候將其消滅。因此成吉思汗大力追剿殘餘勢力。特別是宿敵札木合、脫脫二人及朵兒邊部，絕對不能放過。
「不管怎麼樣，都要把札木合和脫脫給我找出來。」成吉思汗下令。只要札木合還活著，成吉思汗便寢食難安。
一二〇四年的秋天，成吉思汗將脫脫追到了阿爾泰山中的合剌答勒，大敗脫脫率領的殘軍，但是脫脫本人和他的兒子忽都和赤剌溫逃脫了。此時，蔑兒乞部的殘餘勢力投降。蔑兒乞一個分支的首領答亦兒兀孫為了表示自已的誠意，想要將女兒忽蘭獻給成吉思汗。
在前往投降途中，答亦兒兀孫和忽蘭一行遇到了合撒兒的軍隊。
「等等！你們是什麼人？」
被合撒兒的軍隊團團圍住的答亦兒兀孫說，要將自己的女兒獻給成吉思汗。合撒兒聞聽此言，看了看美麗的忽蘭，非常驚訝，說道：「把這樣漂亮的女兒帶到戰場上，豈不是把羊兒送進餓狼群？現在戰爭剛剛結束，將士們還沒平靜下來。你們先在我這裡住下，等形勢稍微穩定之後再走吧。」
於是，答亦兒兀孫和忽蘭父女二人便在合撒兒帳中住了三天。
合撒兒的做法是正確的。因為戰爭剛剛結束，將士們還在追殺殘兵。火焰熄滅之後，還會有小火苗從灰燼中竄出，倖存下來的乃蠻士兵集結成小隊，仍在進行絕望的抵抗，小規模的戰鬥還在繼續。在戰鬥結束的地方，士兵們開始掠奪和強姦。這是戰後的娛樂，是被允許的。
第四天，合撒兒見混亂的局面有所好轉，便帶著忽蘭來到成吉思汗面前。
成吉思汗看到忽蘭的美貌，驚呆了。破衫爛衣、渾身的泥土，都無法掩蓋她的天姿國色。如果說古兒別速是雍容的牡丹，那麼忽蘭便是在峽谷間悄無聲息開放的百合或勿忘草，楚楚可憐，氣質高雅，凜凜有節。
雖然是來降，忽蘭卻面無懼色。雖然知道自己不過是父親送給成吉思汗的禮物，但是，她沒有像其他人一樣跪倒在成吉思汗面前，乞求饒命，而是揚起雙眉，面無懼色地看著他。
成吉思汗從這個頭髮凌亂、滿身污垢、身上帶著傷的少女身上看到了—縷光輝。
第一次看到孛兒帖，後來見到也遂和也速干，以及看到古兒別速的時候，他都只是被她們的美貌吸引，但並沒有在她們身上看到光輝。成吉思汗突然感覺自己想要拜倒在這個少女腳下。
「你叫什麼名字？」其實成吉思汗已經從合撒兒口中知道了她的名字，但是為了鎮定心緒，他佯裝不知，又問了一遍。
「忽蘭。」少女的回答很簡短。
「你難道不怕我？」
以答亦兒兀孫為首的蔑兒乞氏的每一個俘虜，都在成吉思汗面前蜷縮著身子，膽戰心驚地看著成吉思汗的臉色，只有忽蘭一人面無懼色，緊緊地盯著成吉思汗。
「害怕。但是我要是畏懼的話，父親將我獻給您也就沒有意義了。父親和部眾的性命都指望我呢。」忽蘭毫不畏懼地答道。
「你是說願意把自己獻給我嗎？」成吉思汗苦笑。
「女人沒有思想，任憑您的處置。」忽蘭說道。
聽了這句話，成吉思汗想到了母親訶額侖，忽蘭也和她一樣，可以為任何男人生孩子。
但是，即便都是生孩子的工具，這樣清純而高雅的女人孕育出來的種子肯定不同尋常。從這個女孩身上的光茫，成吉思汗看到了這一點。成吉思汗開始擔心這個女孩是否已經在戰場上被飢餓的狼群玷污。
「你為什麼截住他們，在你家中住了三天？」成吉思汗質問合撒兒。他懷疑合撒兒已將忽蘭玷污。此時合撒兒若回答不當，很可能受到懲罰。
合撒兒還沒有說話，忽蘭便替他辯護道：「我們前來的途中遇見了合撒兒。他勸阻了我們，說戰爭剛剛結束，戰場上還很混亂，將士們殺氣騰騰，要是繼續前進，不知道會碰到什麼事，於是建議我們留在他營中。要是沒有遇見合撒兒，說不定現在我已經被士兵們強暴，其他人也都被殺了。合撒兒是我們的救命恩人。您要是懷疑的話，就親自來檢驗一下我的身體。」
合撒兒道：「我發誓自己乃忠誠於可汗之人。不管遇見多麼美貌的女人，不管得到怎樣珍貴的駿馬和昂貴的財物，都要敬獻給可汗，因為這些都屬於可汗。我跟自己的部下也這樣說。您要是還懷疑的話，我便以死來證明清白！」
成吉思汗相信了他，又被忽蘭所感動，便道：「原諒我，我不是懷疑你的忠誠，只是在擔心忽蘭。」
成吉思汗向合撒兒道了歉，將忽蘭收為自己的第五個妃子，此後，在成吉思汗後宮，忽蘭最為得寵，每次出征，他都會帶著她。
成吉思汗決定清掃草原上所有反對他的勢力。
在這些殘餘勢力當中，最為頑強的是脫脫率領的蔑兒乞人。他和他的兩個兒子忽都、赤剌溫一起在台合勒山中修築要塞，進行頑強的抵抗。
成吉思汗派出赤白去追剿。赤白初次擔此大任，異常興奮，一舉將台合勒山寨拿下，完成了任務。
脫脫帶著兩個兒子和一些士兵逃脫。成吉思汗派人繼續追擊，直到冬天，由於下雪，無法行軍，成吉思汗只得作罷，等待明春。
一二〇五年一整年，成吉思汗都在為確立和鞏固自己的霸權進行著這種清掃殘餘勢力的戰鬥。
一二〇四年末開始，成吉思汗在阿爾泰山南麓度過了冬天。翌年春天，成吉思汗對聚集在也爾的石河一帶的太陽汗的兒子屈出律、蔑兒乞的脫脫及其三個兒子發起進攻。
在這次戰爭中，成吉思汗軍大敗蔑兒乞和乃蠻的殘軍。而且，在第一次被成吉思汗打敗之後便一直與成吉思汗對抗的脫脫也在這次戰鬥中中箭身亡。
脫脫的兒子忽都、赤剌溫沒能將脫脫的遺體從戰場上搬出來，只能砍下他的頭顱帶走了。
成吉思汗從服裝和屍體的特徵判斷出那具無頭屍乃是自己的宿敵，不禁感到幾分悲傷，遂將他隆重安葬在河畔。
乃蠻和蔑兒乞的殘兵為了躲避成吉思汗的追殺，在渡過也爾的石河的時候，又有很多人溺水身亡。
忽都、赤剌溫二人逃到了也爾的石河以西的大草原。屈出律則投奔了西遼的古兒汗。
成吉思汗將俘虜的忽都之妻脫列哥那賜給了窩闊台。她就是日後成為蒙古帝國第三代大汗貴由汗（定宗）的母親。
成吉思汗依然沒有放鬆對殘敵的追殺，為了徹底消滅脫脫的三個兒子，他派出了速不台，並賜給他鐵戰車。
成吉思汗的「鐵車之敕」大意如下：「脫脫的兒子就像是牧馬人鞭下的馬兒、中箭的鹿兒，想要倉皇逃走。他們要是變成鳥兒逃到天空，你就變成蒼鷹去追趕。他們要是變成鼠兒遁入地下，你就變成鐵鍬把他們挖出來。他們要是變成了魚兒，你就變成網將他們捕捉。翻越高山，渡過大河，廣闊的草原任你馳騁。不要餓著戰馬，在糧食用盡之前要將它養肥。糧食用盡，就為時已晚了。在你前方的草原上，有很多猛獸，不要帶著部隊向有猛獸的地方前進。不用拴上馬嚼，讓我們的戰馬盡情地呼嘯。不服從命令者任你懲罰，遇見可疑的人便當場殺掉。即便到了河的對岸，抑或是大山的彼方，也不必擔心。不管你在哪裡，只要想著我在你的身邊，便會得到長生天的保佑。」
他慷慨激昂地對速不台說了這番話。
速不台大受鼓舞，領了成吉思汗的旨意，帶兵出發，他最終在楚河河畔將蔑兒乞的殘兵殲滅。
至此，在成吉思汗毫不留情的掃蕩之下，多年的宿敵蔑兒乞部終於被徹底消滅。剰下的，只有札木合了。
札木合帶著僅存的五個部下躲進了阿爾泰山脈東北部的儻魯山中，在那裡落草為寇。
他已經失去了所有的牛羊，靠獵取野山羊苟延殘喘。別說和成吉思汗對抗，現在就是要生存下去也變得異常困難。
脫脫已經被殺，屈出律也逃到了西遼，塔塔兒、泰亦赤兀、弘吉剌、朵兒邊和札答蘭等部的殘餘悉數投靠了成吉思汗。
曾經和成吉思汗結為安答，又率領數萬大軍與成吉思汗爭霸的札木合已經沒有任何希望，就像一隻在山中晃來晃去覓食的小動物，灰心喪氣。曾經不屈不撓的札木合，如今已經完全沒有了鬥志，每天只是在和飢餓作鬥爭。
有一天，他從儻魯山中打獵回來，見五個部下正吃著先前打來的山羊，怒道：「主人還在山中打獵，你們卻先吃上了。真是沒