铁木真登上汗位之初，其家族的兀鲁思只控制着怯绿连河上游不大的地域，属众也不多。而蒙古诸部中的泰赤乌、札答兰等部的实力都在他之上。要巩固自己的地位，使蒙古诸强部都承认其权力，他仍然需要强大的克烈部首领王罕的支持。因此，即位后，他立即派遣答孩、速格该二人向王罕报告，并得到了王罕的认可。他的崛起，理所当然地引起了泰赤乌部贵族和札答兰部首领札木合的不安、不满与仇视，因为他们既不愿看到、也不能容忍出现一个新的、强大的、足以与他们抗衡的势力。因而，蒙古各部贵族间的一场战争也就在所难免。于是，以札木合之弟绐察儿①抢劫铁木真马匹被射杀的事件为导火线，引发了铁木真与札木合、泰赤乌部贵族间的一场战争——十三翼之战。
时给察儿居玉律哥泉②。一日，率众至萨里川，将成吉思汗的马群劫走。成吉思汗的伴当拙赤答儿马剌连夜追赶，至马群，暗伏马上，箭射给察儿致死。以此之故，札木合联合泰赤乌部贵族，起兵3万，分十三翼进攻成吉思汗。时成吉思汗驻营于古连勒古地方，得到札木合部下亦乞列思族人木勒客脱塔黑、孛罗勒歹二人的报告③，立即组织起自己的军队总共3万人编成十三翼，阵于答兰版朱思之野（又作答兰巴勒主惕、答兰巴勒渚思），准备迎击。十三翼即十三个古列延④，其中第一翼为成吉思汗的母亲诃额伦率领的亲族、部属、侍臣、仆役和属于她个人所有的人们；第二翼成吉思汗自己统领的诸子、那可儿和护卫队；第三翼至第十一翼是乞颜氏各贵族率领的族人和属民；十二、十三两翼由来附的旁支尼鲁温氏族成员组成⑤。这就是成吉思汗的全部武装力量。
经过激战，成吉思汗溃败，退至斡难河的哲列捏狭地⑥。札木合获胜回军，对赤那思族（也称捏古思族，为坚都赤那和兀鲁克臣赤那的后裔）即成吉思汗的第十三翼进行了残酷的屠杀，将其部众煮了70大锅，又砍下察合安的头，系在马尾上拖着。由于札木合性情残暴，军纪不严，虽然取得了胜利，而各部首领却纷纷离他而去，归附了成吉思汗。当时，诸部之中“唯泰赤乌地广民众，号为最强”。但其“内无统纪”，各强支之间互争雄长，不能统一；贵族、首领对部众又十分凶残，常攘其车马，夺其饮食，无人君之度。
成吉思汗像与他们的残忍骄横态度相反，成吉思汗则采取了笼络人心的作法。有泰赤乌属部照烈部（又作沼兀列惕）与成吉思汗所居营盘邻近。一日，成吉思汗出猎，偶与照烈部猎骑相属，由于他们没带锅和粮食，成吉思汗遂邀他们同宿，凡留者，悉与饮食。翌日再围猎，他又令左右将野兽驱人照烈部的猎场，使其满载而归，部众不胜感激。照烈之长玉律为泰赤乌贵族欺凌，不堪忍受，遂与塔海答鲁率所部来归。他们对成吉思汗说：“我们如同无夫之妇，无主之马群，无牧人之畜群。长母之诸子（指泰赤乌部贵族）正在毁灭我们，为了你的友谊，让我们一起用剑去作战，去歼灭你的敌人！”⑦成吉思汗听后大受启发，因说道：“如我熟寐，摔发而悟之；兀坐，掀髯而起之。汝之言，我素心也，汝兵车所至，余悉力而助也。”遂与之结盟。后玉律和塔海答鲁二人食言叛去。其族人忽敦忽儿章⑧怨其反侧，遂杀之。此后，成吉思汗对部属愈加宽仁、关怀和加意笼络。时札木合和泰赤乌贵族的部属多苦其主非法，见成吉思汗仁义，有人君之度，“衣人以己衣，乘人以己马”，以为“安民定国，必此人”。于是兀鲁兀惕、忙忽惕（忙兀）、晃豁坛、速勒都思等族以及主儿扯歹（术赤台）、忽余勒答儿（畏答儿）、蒙力克诸人，纷纷来附。十三翼之战，成吉思汗虽败犹胜，实力反而因此壮大。接踵而至的又一次机遇，使成吉思汗的威望空前提高。这就是他与王罕联兵配合金朝夹攻塔塔儿部的斡里札河之战⑨。
自金初以来，金朝一直利用塔塔儿部为他们防卫东北路边墙，使之与其他各部互相牵制，在金朝与蒙古各部之间起一种缓冲作用。塔塔儿部是一个人数众多、强大、富有的部落，它长期为金朝属部，在金朝的支持、挑动下，经常攻击蒙古、克烈等部。合不勒汗长子斡勤巴儿合黑和俺巴孩等曾被他们执送金朝，处以“木驴”之刑，也速该又被他们毒死，两部遂成世仇。金章宗明昌六年（¨95），蒙古部落山只昆（散只兀）、合答斤（合底斤）联合翁吉剌等部，侵扰金朝边境，金遣夹谷清臣率师北伐，以轻骑8千，令宣徽使移剌敏为都统，左卫将军完颜充、招讨使完颜安国为左、右翼，分领前队，清臣自选精兵1万以当后队。并征召诸牂部族军从征。金军进至合勒河（今哈拉哈河），前队移剌敏等于栲栳泊（今呼伦湖）攻下14营寨，回迎清臣大军。塔塔儿部（北阻鞍）乘金军回师之机，拦夺其所获羊马以归。清臣则遣人责其赕罚，塔塔儿首领蔑古真薛古勒图（又作蔑儿真速勒图）因此反叛。金章宗责清臣贪小利而失大局，命右丞相完颜襄代之。承安元年（1196），完颜襄（《元朝秘史》作王京）兵分两路北征，东路军进至龙驹河（今克鲁伦河），为塔塔儿所围，三日不得出。完颜襄率兵往援，鸣鼓夜发，清晨突袭，塔塔儿溃败，部众向斡里札河退却。完颜襄遣安国追击⑩。
成吉思汗得讯，立即报告王罕，邀他出兵共同配合金朝夹击塔塔儿。并以“为父祖复仇”的名义，征集长支主儿乞部撒察别乞、泰出等族人助战。主儿乞氏没有出兵，成吉思汗遂率领自己的一个古列延人马与王罕军会合，引军自斡难河上游东进，至斡里札河的忽速秃失秃延、纳剌秃失秃延之野，协助金军击溃塔塔儿，攻破两寨，捕杀其首领蔑古真薛兀勒图（又作灭兀真笑里徒、蔑兀真速勒图），“尽虏其车马粮饷”，“又获大珠裘、银绷车各一”。在这次掠夺中，他们还虏获了“银摇车和饰有珠宝的被子”。由于当时这种奢侈品在蒙古人中间很少，因此，这件事被认为是很了不起的大事。在抢劫塔塔儿人寨子时，还拾到一个带着金圈环子、穿着金纻丝貂皮里兜肚的小孩。给诃额伦做了养子。他就是后来著名的大断事官失吉忽秃忽（又作忽都忽、忽都虎、失乞刊忽都忽）。
斡里札河之战的胜利，不仅使成吉思汗有力地打击了劲敌，使世仇塔塔儿部从此一蹶不振，而且在蒙古部中赢得了能“为父祖报仇”的崇高声望。同时，他和王罕也得到了金朝的封赏，金授成吉思汗“札兀惕忽里”（牂军首领）之职。王罕则得到“王”的封号。王罕本名脱斡邻勒（又作脱里）。自被金朝封为“王”，始在“罕”（汗）号之上加“王”，而有“王罕”之称。
金朝的封赏大大提高了成吉思汗的权力，从此他可以用朝廷命官的身份号令蒙古部众和统辖其他贵族。同时，也缓和了蒙古部和金朝的矛盾，为他统一蒙古各部创造了有利条件。
斡里札河之战前蒙古部贵族内部就已经出现裂痕。合不勒汗长子一支，即乞颜一主儿乞氏依恃长支族望和所继承的精悍部众，小视把儿坛把阿秃儿的子孙。撒察别乞、泰出等长支贵族虽然推举铁木真为汗但并不情愿服从他的管辖，而且一直怀有争夺权位的野心。一次在斡难河边树林中举行的亲族宴会上，撒察别乞的母亲责打了成吉思汗的司厨失乞兀儿（又作失丘儿、失邱儿）；主儿乞氏掌管马匹的不里孛阔砍伤了为成吉思汗管理马匹的别勒古台。两家因此而发生了一场争斗。这两件小事暴露了成吉思汗与长支贵族的矛盾，同时，也使他意识到主儿乞氏是他的危险对手。攻打塔塔儿时，主儿乞氏非但不肯出兵，反而乘成吉思汗率兵出征之机，劫掠了他的奥鲁，违背了当初推举可汗的盟约。于是，成吉思汗以此为理由，于1197年从斡里札河回军后，乘胜征讨主儿乞氏。主儿乞氏人的营盘在客鲁连河上游的朵罗安孛勒答兀之地（又作朵栾一盘陀山、朵兰孛一孛勒答黑，今蒙古境内克鲁伦河与臣赫尔河合流点之西的巴颜乌兰山南麓）。成吉思汗军至，主儿乞即溃，撒察别乞、泰出等料不能敌，带少数人逃跑，至帖列秃地方，被成吉思汗捉获处死。以前合不勒汗挑选出来授与长子的“有胆有勇的百姓”，全部被成吉思汗兼并，成为他的“梯己百姓”。札剌亦儿族的古温兀阿（又作孔温窟哇），赤剌温孩亦赤兄弟分别带领二子模合里（木华黎）、不合和统格、合失来投成吉思汗，为其“永远做奴婢”、“看守金门”。赤列温又将第三子者卜客送与成吉思汗弟合撒儿。者卜客于主儿乞的营盘内拾得一个许兀慎族的小孩，名叫孛罗兀勒（又作博尔忽、博尔浑、博罗欢），也被诃额伦收为养子，成为后来的“四杰”之一。攻灭亲族中最有势力的长支贵族，大大提高和巩固了成吉思汗的权力，这是他迈向成功之路的重要一步。此后，他不断地削弱蒙古部中其他贵族的权力、地位，迫使他们逐渐降为从属于他的一般那可儿。
驻牧于阔连海子（今呼伦湖）之东的翁吉剌、合答斤、山只昆等部落，屡扰金朝边塞。承安三年（1198），金朝在击溃塔塔儿人的反叛之后，“乘其春暮马弱”，遣宗浩、襄等率兵进剿三部。先破翁吉剌，后合答斤部长白古带，山只昆部长胡必剌等亦降。这些“桀傲不驯”的部落受到重创，力量大大削弱。金朝的统治此时也已由盛转衰，无力继续控制蒙古草原。这一形势为以后成吉思汗东进夺取东部地区（今内蒙古呼伦贝尔草原一带）显然是有利的。
主儿乞氏被吞并之后，泰赤乌氏贵族即成为与成吉思汗争夺蒙古汗权和部众的主要对手。1200年春，成吉思汗与王罕会于萨里川，共同起兵攻打泰赤乌部。泰赤乌贵族沆忽阿忽出、忽怜、忽都答儿、塔儿忽台乞邻勒秃黑（“塔儿忽台”为名，“乞邻勒秃黑”意为：“嫉妒者”）等则与蔑儿乞贵族联合。此前逃往巴儿忽真隘的蔑儿乞部长脱黑脱阿（又作脱脱、脱黑台别乞）遣其子忽都等统兵助泰赤乌，双方会战于斡难河。泰赤乌部战败，退至月良兀秃剌思（又作月良古惕秃剌思）之野（今俄罗斯赤塔南之鄂良古依河地），整军再战。经过激战，泰赤乌终于被击溃，塔儿忽台、忽都答儿等被擒杀，沆忽阿忽出与忽都等逃人巴儿忽真隘，忽怜投奔乃蛮部。
主儿乞氏和泰赤乌氏是蒙古贵族中两支强大势力，他们的相继灭亡和溃散，使成吉思汗地位得以巩固，实力进一步壮大。
泰赤乌部被消灭后，成吉思汗的进取目标转向东都。合答斤、山只昆两族，根据蒙古祖先传说，是朵奔蔑儿干死后，阿阑豁阿感天光而生的二子不忽合塔吉和不合秃撒勒只的后裔，与成吉思汗具有同样尊贵的血统。他们本来也是强大的蒙古部落。1198年被金朝击溃，严重受挫，实力已大不如前。先是，成吉思汗曾遣使通好二部，欲与之联合，他们没有接受，对来使也缺乏应有的尊敬，他们从锅里将连同羊血煮在一起的……那样的羊的脏腑取出，泼在他的脸上，辱骂了他，使他受辱而归，由此双方结下了仇怨。其后，他们又依附泰赤乌，参与反对成吉思汗。泰赤乌失败后，他们的首领又与塔塔儿，朵儿边和翁吉剌等部会于阿雷泉（今海拉尔河下游北），斩白马为誓，谋袭成吉思汗与王罕。
成吉思汗得到其岳父特薛禅的密报，即与王罕率军自斡难河附近的虎图泽出发，与合答斤诸部军战于歪亦剌川（今页尔湖），大败敌军。成吉思汗、王罕大掠其牲畜、部众而去。成吉思汗驻军于金边墙附近的彻彻儿山，继续攻伐这一带的塔塔儿部。
1201年，札木合纠集一批败散的贵族，包括塔塔儿、翁吉剌、合答斤、山只昆、泰赤乌、朵儿边、豁罗剌思、亦乞列思、蔑儿乞、斡亦剌、乃蛮等11部，会于犍河，共立札木合为古儿汗。各部首领为维护各自的贵族地位而结成了一个松散的联盟。他们在秃律别儿河（今得尔布干河）岸发誓：“凡我同盟，有浅此谋者，如岸之摧，如林之伐。”誓毕，共举足踏岸，挥刀砍林，驱众驰马往攻成吉思汗。时札木合军中有名为塔海哈者，悉知其谋，他与成吉思汗的部属召烈氏抄兀儿相亲，值抄兀儿前往探视，二人骑马并行，塔海哈以马鞭掇其肋，抄兀儿回顾，塔海哈示之以目，抄兀儿会其意，下马佯为小便，塔海哈遂告以札木合等之谋。抄兀儿当即驰还。途经豁罗剌思（又作火鲁剌思、火鲁剌、火罗剌思、豁里剌儿等）部，首领也速该命其家人火力台与抄兀儿同往报告，成吉思汗闻讯，即刻起兵迎战。在海剌儿河（今海拉尔河）支流帖尼火罗罕（火罗罕意为“小河”）之地，击溃札木合联军。札木合逃走，翁吉剌部来附，其余诸部首领则作鸟兽散。打败札木合后，成吉思汗又于1202年（金泰和二年，宋嘉泰二年）出兵征讨答阑捏木儿格思（今蒙古东方省贝尔湖南讷墨尔根地）的按赤塔塔儿、察罕塔塔儿、都塔兀惕塔塔儿、阿鲁孩塔塔儿等部，追击至兀鲁回·失连真河（又作兀勒灰失鲁格勒只惕，今内蒙古东乌珠穆沁旗乌兰盖郭勒、色也勒钦郭勒）一带，将塔塔儿部尽数消灭，控制了东部地区。
当成吉思汗征讨塔塔儿诸部时，王罕率众追剿蔑儿乞部，至八儿忽真脱窟木之地，将脱黑脱阿长子脱古思别乞杀死，又虏其二女忽秃黑台、察阿仑和二子忽图、赤剌温及其妻子，洗劫了财物、部众。
初，乃蛮太阳罕弟歪禄罕（又作不亦鲁黑罕、不欲鲁罕、卜欲鲁罕）在黑辛八石（今新疆乌伦古湖或布伦托海）一带被成吉思汗和王罕击败，逃往谦谦州地区（在唐麓岭以北，谦河上游流域，叶尼塞河上游一带）。1202年秋，他与蔑儿乞部的脱黑脱阿和斡亦剌部的忽都合别乞等合兵东进，攻打成吉思汗和王罕。这时，札木合与泰赤乌、朵儿边、合答斤、山只昆、塔塔儿等部残余势力，也与歪禄罕联合起来，一时声势夺人。成吉思汗、王罕军避其锋芒，自兀鲁回·失连真河地区退入兀惕古城墙（金边墙），王罕子亦剌合居侧翼，据高山结营，乃蛮军冲击不能下，遂还。亦剌合也人塞。
战前，成吉思汗移辎重于他处，与王罕依阿兰塞为壁。待歪禄罕联军进至阙亦坛之野，两军会战。成吉思汗和王罕凭据有利地势。而歪禄罕联军由于寒气凛冽，又值大风雪，许多部属手足冻裂，人畜从高处滚下，填沟坠堑，死伤甚多，军乱不能战，被迫引兵退回。札木合等各部起兵来援乃蛮，见势不利，未战即星散离去。王罕追击至额湎古涅河，札木合无力抵抗，举兵投降。泰赤乌部首领阿兀出把阿秃儿等率众渡过斡难河，成吉思汗追至，双方连战数次，胜负未决。在战斗中，成吉思汗颈部中流矢，蒙古军被迫休战，泰赤乌军也连夜离开。成吉思汗被伤，流血不止。那可儿者勒蔑用口为其吮吸淤血。夜半，成吉思汗醒来后口渴，者勒蔑裸身独祷祷潜入敌营，寻找马奶子不得，拿回一桶酪（酸奶子）。又弄来一些水，与酪调后给他喝。成吉思汗问者勒蔑何以裸身前去，者勒蔑说：“我若被擒，就说我本是来投降你们的，但被他们发觉，将我的衣服脱去，欲杀间，遂挣脱逃出来。”成吉思汗伤愈后，立即率军追击泰赤乌。阿兀出把阿秃儿、豁团斡儿昌、忽都兀答儿及其家属皆被执处死。部众全部降服。