鐵木真登上汗位之初，其家族的兀魯思只控制著怯綠連河上游不大的地域，屬眾也不多。而蒙古諸部中的泰赤烏、札答蘭等部的實力都在他之上。要鞏固自己的地位，使蒙古諸強部都承認其權力，他仍然需要強大的克烈部首領王罕的支持。因此，即位后，他立即派遣答孩、速格該二人向王罕報告，并得到了王罕的認可。他的崛起，理所當然地引起了泰赤烏部貴族和札答蘭部首領札木合的不安、不滿與仇視，因為他們既不愿看到、也不能容忍出現一個新的、強大的、足以與他們抗衡的勢力。因而，蒙古各部貴族間的一場戰爭也就在所難免。于是，以札木合之弟紿察兒①搶劫鐵木真馬匹被射殺的事件為導火線，引發了鐵木真與札木合、泰赤烏部貴族間的一場戰爭——十三翼之戰。

時給察兒居玉律哥泉②。一日，率眾至薩里川，將成吉思汗的馬群劫走。成吉思汗的伴當拙赤答兒馬剌連夜追趕，至馬群，暗伏馬上，箭射給察兒致死。以此之故，札木合聯合泰赤烏部貴族，起兵3萬，分十三翼進攻成吉思汗。時成吉思汗駐營于古連勒古地方，得到札木合部下亦乞列思族人木勒客脫塔黑、孛羅勒歹二人的報告③，立即組織起自己的軍隊總共3萬人編成十三翼，陣于答蘭版朱思之野（又作答蘭巴勒主惕、答蘭巴勒渚思），準備迎擊。十三翼即十三個古列延④，其中第一翼為成吉思汗的母親訶額倫率領的親族、部屬、侍臣、仆役和屬于她個人所有的人們；第二翼成吉思汗自己統領的諸子、那可兒和護衛隊；第三翼至第十一翼是乞顏氏各貴族率領的族人和屬民；十二、十三兩翼由來附的旁支尼魯溫氏族成員組成⑤。這就是成吉思汗的全部武裝力量。

經過激戰，成吉思汗潰敗，退至斡難河的哲列捏狹地⑥。札木合獲勝回軍，對赤那思族（也稱捏古思族，為堅都赤那和兀魯克臣赤那的后裔）即成吉思汗的第十三翼進行了殘酷的屠殺，將其部眾煮了70大鍋，又砍下察合安的頭，系在馬尾上拖著。由于札木合性情殘暴，軍紀不嚴，雖然取得了勝利，而各部首領卻紛紛離他而去，歸附了成吉思汗。當時，諸部之中“唯泰赤烏地廣民眾，號為最強”。但其“內無統紀”，各強支之間互爭雄長，不能統一；貴族、首領對部眾又十分兇殘，常攘其車馬，奪其飲食，無人君之度。

成吉思汗像與他們的殘忍驕橫態度相反，成吉思汗則采取了籠絡人心的作法。有泰赤烏屬部照烈部（又作沼兀列惕）與成吉思汗所居營盤鄰近。一日，成吉思汗出獵，偶與照烈部獵騎相屬，由于他們沒帶鍋和糧食，成吉思汗遂邀他們同宿，凡留者，悉與飲食。翌日再圍獵，他又令左右將野獸驅人照烈部的獵場，使其滿載而歸，部眾不勝感激。照烈之長玉律為泰赤烏貴族欺凌，不堪忍受，遂與塔海答魯率所部來歸。他們對成吉思汗說：“我們如同無夫之婦，無主之馬群，無牧人之畜群。長母之諸子（指泰赤烏部貴族）正在毀滅我們，為了你的友誼，讓我們一起用劍去作戰，去殲滅你的敵人！”⑦成吉思汗聽后大受啟發，因說道：“如我熟寐，摔發而悟之；兀坐，掀髯而起之。汝之言，我素心也，汝兵車所至，余悉力而助也。”遂與之結盟。后玉律和塔海答魯二人食言叛去。其族人忽敦忽兒章⑧怨其反側，遂殺之。此后，成吉思汗對部屬愈加寬仁、關懷和加意籠絡。時札木合和泰赤烏貴族的部屬多苦其主非法，見成吉思汗仁義，有人君之度，“衣人以己衣，乘人以己馬”，以為“安民定國，必此人”。于是兀魯兀惕、忙忽惕（忙兀）、晃豁壇、速勒都思等族以及主兒扯歹（術赤臺）、忽余勒答兒（畏答兒）、蒙力克諸人，紛紛來附。十三翼之戰，成吉思汗雖敗猶勝，實力反而因此壯大。接踵而至的又一次機遇，使成吉思汗的威望空前提高。這就是他與王罕聯兵配合金朝夾攻塔塔兒部的斡里札河之戰⑨。

自金初以來，金朝一直利用塔塔兒部為他們防衛東北路邊墻，使之與其他各部互相牽制，在金朝與蒙古各部之間起一種緩沖作用。塔塔兒部是一個人數眾多、強大、富有的部落，它長期為金朝屬部，在金朝的支持、挑動下，經常攻擊蒙古、克烈等部。合不勒汗長子斡勤巴兒合黑和俺巴孩等曾被他們執送金朝，處以“木驢”之刑，也速該又被他們毒死，兩部遂成世仇。金章宗明昌六年（¨95），蒙古部落山只昆（散只兀）、合答斤（合底斤）聯合翁吉剌等部，侵擾金朝邊境，金遣夾谷清臣率師北伐，以輕騎8千，令宣徽使移剌敏為都統，左衛將軍完顏充、招討使完顏安國為左、右翼，分領前隊，清臣自選精兵1萬以當后隊。并征召諸牂部族軍從征。金軍進至合勒河（今哈拉哈河），前隊移剌敏等于栲栳泊（今呼倫湖）攻下14營寨，回迎清臣大軍。塔塔兒部（北阻鞍）乘金軍回師之機，攔奪其所獲羊馬以歸。清臣則遣人責其賧罰，塔塔兒首領蔑古真薛古勒圖（又作蔑兒真速勒圖）因此反叛。金章宗責清臣貪小利而失大局，命右丞相完顏襄代之。承安元年（1196），完顏襄（《元朝秘史》作王京）兵分兩路北征，東路軍進至龍駒河（今克魯倫河），為塔塔兒所圍，三日不得出。完顏襄率兵往援，鳴鼓夜發，清晨突襲，塔塔兒潰敗，部眾向斡里札河退卻。完顏襄遣安國追擊⑩。

成吉思汗得訊，立即報告王罕，邀他出兵共同配合金朝夾擊塔塔兒。并以“為父祖復仇”的名義，征集長支主兒乞部撒察別乞、泰出等族人助戰。主兒乞氏沒有出兵，成吉思汗遂率領自己的一個古列延人馬與王罕軍會合，引軍自斡難河上游東進，至斡里札河的忽速禿失禿延、納剌禿失禿延之野，協助金軍擊潰塔塔兒，攻破兩寨，捕殺其首領蔑古真薛兀勒圖（又作滅兀真笑里徒、蔑兀真速勒圖），“盡虜其車馬糧餉”，“又獲大珠裘、銀繃車各一”。在這次掠奪中，他們還虜獲了“銀搖車和飾有珠寶的被子”。由于當時這種奢侈品在蒙古人中間很少，因此，這件事被認為是很了不起的大事。在搶劫塔塔兒人寨子時，還拾到一個帶著金圈環子、穿著金纻絲貂皮里兜肚的小孩。給訶額倫做了養子。他就是后來著名的大斷事官失吉忽禿忽（又作忽都忽、忽都虎、失乞刊忽都忽）。

斡里札河之戰的勝利，不僅使成吉思汗有力地打擊了勁敵，使世仇塔塔兒部從此一蹶不振，而且在蒙古部中贏得了能“為父祖報仇”的崇高聲望。同時，他和王罕也得到了金朝的封賞，金授成吉思汗“札兀惕忽里”（牂軍首領）之職。王罕則得到“王”的封號。王罕本名脫斡鄰勒（又作脫里）。自被金朝封為“王”，始在“罕”（汗）號之上加“王”，而有“王罕”之稱。

金朝的封賞大大提高了成吉思汗的權力，從此他可以用朝廷命官的身份號令蒙古部眾和統轄其他貴族。同時，也緩和了蒙古部和金朝的矛盾，為他統一蒙古各部創造了有利條件。

斡里札河之戰前蒙古部貴族內部就已經出現裂痕。合不勒汗長子一支，即乞顏一主兒乞氏依恃長支族望和所繼承的精悍部眾，小視把兒壇把阿禿兒的子孫。撒察別乞、泰出等長支貴族雖然推舉鐵木真為汗但并不情愿服從他的管轄，而且一直懷有爭奪權位的野心。一次在斡難河邊樹林中舉行的親族宴會上，撒察別乞的母親責打了成吉思汗的司廚失乞兀兒（又作失丘兒、失邱兒）；主兒乞氏掌管馬匹的不里孛闊砍傷了為成吉思汗管理馬匹的別勒古臺。兩家因此而發生了一場爭斗。這兩件小事暴露了成吉思汗與長支貴族的矛盾，同時，也使他意識到主兒乞氏是他的危險對手。攻打塔塔兒時，主兒乞氏非但不肯出兵，反而乘成吉思汗率兵出征之機，劫掠了他的奧魯，違背了當初推舉可汗的盟約。于是，成吉思汗以此為理由，于1197年從斡里札河回軍后，乘勝征討主兒乞氏。主兒乞氏人的營盤在客魯連河上游的朵羅安孛勒答兀之地（又作朵欒一盤陀山、朵蘭孛一孛勒答黑，今蒙古境內克魯倫河與臣赫爾河合流點之西的巴顏烏蘭山南麓）。成吉思汗軍至，主兒乞即潰，撒察別乞、泰出等料不能敵，帶少數人逃跑，至帖列禿地方，被成吉思汗捉獲處死。以前合不勒汗挑選出來授與長子的“有膽有勇的百姓”，全部被成吉思汗兼并，成為他的“梯己百姓”。札剌亦兒族的古溫兀阿（又作孔溫窟哇），赤剌溫孩亦赤兄弟分別帶領二子模合里（木華黎）、不合和統格、合失來投成吉思汗，為其“永遠做奴婢”、“看守金門”。赤列溫又將第三子者卜客送與成吉思汗弟合撒兒。者卜客于主兒乞的營盤內拾得一個許兀慎族的小孩，名叫孛羅兀勒（又作博爾忽、博爾渾、博羅歡），也被訶額倫收為養子，成為后來的“四杰”之一。攻滅親族中最有勢力的長支貴族，大大提高和鞏固了成吉思汗的權力，這是他邁向成功之路的重要一步。此后，他不斷地削弱蒙古部中其他貴族的權力、地位，迫使他們逐漸降為從屬于他的一般那可兒。

駐牧于闊連海子（今呼倫湖）之東的翁吉剌、合答斤、山只昆等部落，屢擾金朝邊塞。承安三年（1198），金朝在擊潰塔塔兒人的反叛之后，“乘其春暮馬弱”，遣宗浩、襄等率兵進剿三部。先破翁吉剌，后合答斤部長白古帶，山只昆部長胡必剌等亦降。這些“桀傲不馴”的部落受到重創，力量大大削弱。金朝的統治此時也已由盛轉衰，無力繼續控制蒙古草原。這一形勢為以后成吉思汗東進奪取東部地區（今內蒙古呼倫貝爾草原一帶）顯然是有利的。

主兒乞氏被吞并之后，泰赤烏氏貴族即成為與成吉思汗爭奪蒙古汗權和部眾的主要對手。1200年春，成吉思汗與王罕會于薩里川，共同起兵攻打泰赤烏部。泰赤烏貴族沆忽阿忽出、忽憐、忽都答兒、塔兒忽臺乞鄰勒禿黑（“塔兒忽臺”為名，“乞鄰勒禿黑”意為：“嫉妒者”）等則與蔑兒乞貴族聯合。此前逃往巴兒忽真隘的蔑兒乞部長脫黑脫阿（又作脫脫、脫黑臺別乞）遣其子忽都等統兵助泰赤烏，雙方會戰于斡難河。泰赤烏部戰敗，退至月良兀禿剌思（又作月良古惕禿剌思）之野（今俄羅斯赤塔南之鄂良古依河地），整軍再戰。經過激戰，泰赤烏終于被擊潰，塔兒忽臺、忽都答兒等被擒殺，沆忽阿忽出與忽都等逃人巴兒忽真隘，忽憐投奔乃蠻部。

主兒乞氏和泰赤烏氏是蒙古貴族中兩支強大勢力，他們的相繼滅亡和潰散，使成吉思汗地位得以鞏固，實力進一步壯大。

泰赤烏部被消滅后，成吉思汗的進取目標轉向東都。合答斤、山只昆兩族，根據蒙古祖先傳說，是朵奔蔑兒干死后，阿闌豁阿感天光而生的二子不忽合塔吉和不合禿撒勒只的后裔，與成吉思汗具有同樣尊貴的血統。他們本來也是強大的蒙古部落。1198年被金朝擊潰，嚴重受挫，實力已大不如前。先是，成吉思汗曾遣使通好二部，欲與之聯合，他們沒有接受，對來使也缺乏應有的尊敬，他們從鍋里將連同羊血煮在一起的……那樣的羊的臟腑取出，潑在他的臉上，辱罵了他，使他受辱而歸，由此雙方結下了仇怨。其后，他們又依附泰赤烏，參與反對成吉思汗。泰赤烏失敗后，他們的首領又與塔塔兒，朵兒邊和翁吉剌等部會于阿雷泉（今海拉爾河下游北），斬白馬為誓，謀襲成吉思汗與王罕。

成吉思汗得到其岳父特薛禪的密報，即與王罕率軍自斡難河附近的虎圖澤出發，與合答斤諸部軍戰于歪亦剌川（今頁爾湖），大敗敵軍。成吉思汗、王罕大掠其牲畜、部眾而去。成吉思汗駐軍于金邊墻附近的徹徹兒山，繼續攻伐這一帶的塔塔兒部。

1201年，札木合糾集一批敗散的貴族，包括塔塔兒、翁吉剌、合答斤、山只昆、泰赤烏、朵兒邊、豁羅剌思、亦乞列思、蔑兒乞、斡亦剌、乃蠻等11部，會于犍河，共立札木合為古兒汗。各部首領為維護各自的貴族地位而結成了一個松散的聯盟。他們在禿律別兒河（今得爾布干河）岸發誓：“凡我同盟，有淺此謀者，如岸之摧，如林之伐。”誓畢，共舉足踏岸，揮刀砍林，驅眾馳馬往攻成吉思汗。時札木合軍中有名為塔海哈者，悉知其謀，他與成吉思汗的部屬召烈氏抄兀兒相親，值抄兀兒前往探視，二人騎馬并行，塔海哈以馬鞭掇其肋，抄兀兒回顧，塔海哈示之以目，抄兀兒會其意，下馬佯為小便，塔海哈遂告以札木合等之謀。抄兀兒當即馳還。途經豁羅剌思（又作火魯剌思、火魯剌、火羅剌思、豁里剌兒等）部，首領也速該命其家人火力臺與抄兀兒同往報告，成吉思汗聞訊，即刻起兵迎戰。在海剌兒河（今海拉爾河）支流帖尼火羅罕（火羅罕意為“小河”）之地，擊潰札木合聯軍。札木合逃走，翁吉剌部來附，其余諸部首領則作鳥獸散。打敗札木合后，成吉思汗又于1202年（金泰和二年，宋嘉泰二年）出兵征討答闌捏木兒格思（今蒙古東方省貝爾湖南訥墨爾根地）的按赤塔塔兒、察罕塔塔兒、都塔兀惕塔塔兒、阿魯孩塔塔兒等部，追擊至兀魯回·失連真河（又作兀勒灰失魯格勒只惕，今內蒙古東烏珠穆沁旗烏蘭蓋郭勒、色也勒欽郭勒）一帶，將塔塔兒部盡數消滅，控制了東部地區。

當成吉思汗征討塔塔兒諸部時，王罕率眾追剿蔑兒乞部，至八兒忽真脫窟木之地，將脫黑脫阿長子脫古思別乞殺死，又虜其二女忽禿黑臺、察阿侖和二子忽圖、赤剌溫及其妻子，洗劫了財物、部眾。

初，乃蠻太陽罕弟歪祿罕（又作不亦魯黑罕、不欲魯罕、卜欲魯罕）在黑辛八石（今新疆烏倫古湖或布倫托海）一帶被成吉思汗和王罕擊敗，逃往謙謙州地區（在唐麓嶺以北，謙河上游流域，葉尼塞河上游一帶）。1202年秋，他與蔑兒乞部的脫黑脫阿和斡亦剌部的忽都合別乞等合兵東進，攻打成吉思汗和王罕。這時，札木合與泰赤烏、朵兒邊、合答斤、山只昆、塔塔兒等部殘余勢力，也與歪祿罕聯合起來，一時聲勢奪人。成吉思汗、王罕軍避其鋒芒，自兀魯回·失連真河地區退入兀惕古城墻（金邊墻），王罕子亦剌合居側翼，據高山結營，乃蠻軍沖擊不能下，遂還。亦剌合也人塞。

戰前，成吉思汗移輜重于他處，與王罕依阿蘭塞為壁。待歪祿罕聯軍進至闕亦壇之野，兩軍會戰。成吉思汗和王罕憑據有利地勢。而歪祿罕聯軍由于寒氣凜冽，又值大風雪，許多部屬手足凍裂，人畜從高處滾下，填溝墜塹，死傷甚多，軍亂不能戰，被迫引兵退回。札木合等各部起兵來援乃蠻，見勢不利，未戰即星散離去。王罕追擊至額湎古涅河，札木合無力抵抗，舉兵投降。泰赤烏部首領阿兀出把阿禿兒等率眾渡過斡難河，成吉思汗追至，雙方連戰數次，勝負未決。在戰斗中，成吉思汗頸部中流矢，蒙古軍被迫休戰，泰赤烏軍也連夜離開。成吉思汗被傷，流血不止。那可兒者勒蔑用口為其吮吸淤血。夜半，成吉思汗醒來后口渴，者勒蔑裸身獨禱禱潛入敵營，尋找馬奶子不得，拿回一桶酪（酸奶子）。又弄來一些水，與酪調后給他喝。成吉思汗問者勒蔑何以裸身前去，者勒蔑說：“我若被擒，就說我本是來投降你們的，但被他們發覺，將我的衣服脫去，欲殺間，遂掙脫逃出來。”成吉思汗傷愈后，立即率軍追擊泰赤烏。阿兀出把阿禿兒、豁團斡兒昌、忽都兀答兒及其家屬皆被執處死。部眾全部降服。