金朝丞相完顏襄得到鐵木真和脫斡鄰勒的協助，懲治了反叛的塔塔兒，十分高興，他以皇帝的名義封脫斡裏勒汗為“王”，從此脫斡裏勒汗就稱為“王罕”；封鐵木真為“劄兀惕忽裏”（部落統領），鐵木真正式接受了金朝的封職。
從此脫斡裏勒汗便以“王罕”一名著稱於大漠南北。當時鐵木真的力量不如王罕強大，因此得到的官職不及王罕，但這件事對於他仍有重要作用。鐵木真在蒙古尼倫各部中的威信更高，權力更大，他懲罰和處死了幾個不聽指揮和他作對的奴隸主，並收管了他們的部眾。後來成為成吉思汗“四傑”之一的木華黎就是在這時由他的父親送來做奴隸的。
覆滅泰赤烏部
鐵木真和王罕對外的淩厲攻勢，讓高原諸部深感不安，於是諸部貴族們行動起來，結成聯盟以對抗。1201年，合答斤、散隻兀、朵兒邊、塔塔兒、亦乞列思、弘吉剌、豁羅剌思、乃蠻、篾兒乞、斡亦刺、泰赤烏、劄答闌共12個部的貴族，共推劄木合為“古兒汗”（普眾之汗）。他們揮刀斫林，以表示要與鐵木真、王罕爭戰到底的決心。
這些部落雖然人多勢眾，但是他們來自蒙古高原的四麵八方，更致命的是他們的聯盟，不過是各部貴族為維護自身利益的臨時結合，這樣一班烏合之眾，不可能真正協同作戰。
豁羅剌思部有一個名叫豁裏歹的人，他聽到了劄木合聯軍的密謀。
他擺脫追擊，來到鐵木真處，報告了劄木合等人的密謀。鐵木真立刻通知了王罕，王罕起兵前來會合。鐵木真和王罕的聯軍沿著怯綠連河出發，鐵木真以阿勒壇、忽察兒、答裏台三人為前鋒，王罕以桑昆等人為前鋒，前鋒之前再設探哨。
兩軍終於相遇了，對方是劄木合的先鋒部隊：泰赤烏部的阿兀出把阿禿兒、乃蠻部的不欲魯汗、篾兒乞部脫脫的兒子忽禿、斡亦刺部的忽都合別乞。當時天已黑下來了，於是雙方約定明天再戰。第二天，兩軍在海剌兒河（今海拉爾河）附近展開大戰。經過反複衝殺，劄木合聯軍慘遭失敗，各部貴族把當初的誓言拋之腦後，紛紛帶著潰軍各自逃去。
乃蠻部的不欲魯汗向西方阿勒台山（今阿爾泰山）的自己原住地方向逃去；篾兒乞部的忽禿向薛涼格河（今色楞格河）逃去；泰赤烏部阿兀出把阿禿兒逃往斡難河；斡亦剌部的忽部合別乞退往森林地區。
逃跑途中，劄木合竟大肆搶掠了推舉他為汗的別部百姓，然後向額爾古納河方向逃走。
王罕沿著額爾古納河去追趕劄木合。鐵木真則帶領自己的人馬窮追泰亦烏部的阿兀出把阿禿兒，一直追到斡難河邊。在這裏，阿兀出把阿禿兒收拾殘兵，重新組織力量作困獸之鬥。一場大戰，激烈異常，一直持續到夜幕降臨。雙方相對宿營，準備來日再作決戰。
天大亮以後，人們發現泰赤烏人已經喪失了決戰的勇氣，趁著夜色潰去了，泰赤烏的屬民被拋棄在營地裏，這些屬民都被鐵木真收服。
鐵木真又追及泰赤烏貴族阿兀出把阿禿兒、忽都兀答兒等人，將他們和他們的子孫殺死了。經此一戰，長期與鐵木真為敵的泰赤烏部終於覆滅。
征服東蒙
經過長期的東征西討，鐵木真的力量日益強大起來，他可以依靠自己的軍隊對外進行大規模的戰爭了。1202年的春天，鐵木真出兵開始征討夙敵塔塔兒。六年前的1196年，鐵木真和王罕曾經趁塔塔兒被金朝擊敗之機，幫助金朝重創塔塔兒。一年前的1201年鐵木真和王罕又在抗擊劄木合聯軍時，再次打擊了參與聯軍的塔塔兒。然而塔塔兒盡管多次遭到打擊，喪失了元氣，但仍然擁有相當多的部眾，占據東部與鐵木真為敵。
這一次，鐵木真的目標是塔塔兒的兩個主要部落：察罕塔塔兒、按赤塔塔兒，將他們徹底消滅，穩固地占領蒙古高原東部地區。為了保證戰爭的勝利，也為了一改從前作戰時貴族們貪搶財物，不聽指揮的弊病，在出征之前，鐵木真發布命令說：“打仗的時候，不許搶掠財物，把敵人打敗了，他們的東西都歸我們所有，那時大家再分用。
作戰需後退時，應退向原陣地，退回原陣地後不再肯返身力戰者，斬！”
於是軍紀嚴整，戰鬥力大增。