当时蒙古部中，泰赤乌氏贵族“地广民众，号为最强”（《元史·太祖本纪》），他们自然不能容忍乞颜氏重兴，于是联合札木合，起兵三万进攻铁木真。铁木真方面组成十三翼军队抵抗，其中第一、二翼为母亲月伦兀真和他自己率领的族人和部属，第三至十一翼为乞颜氏各家贵族率领的族人和部属，十二、十三翼为与他联合的旁支尼鲁温部落。从十三翼的组成，可以秘史》及《史集》，其时确有蒙古忽图剌罕兴兵复仇之事。

　　① 据《史集》记载，铁木真妻孛儿帖被掳时已怀孕，后获救回来的路上生下术赤（第1 卷第二册，页68—69）。《蒙古源流》说，铁木真与孛儿帖成婚是在1178 年。孛儿帖生术赤、察合台、窝阔台、拖雷四子和五个女儿。窝阔台生于1186 年，知术赤生年至迟不得晚于1184 年。

　　看出当时铁木真领导下的乞颜氏贵族联盟的结构。两军大战于桑沽儿河附近答兰版朱思（Dalan baljus）之野，铁木真羽翼初长，难以抵敌，率部退到斡难河的一个狭地中①。这就是著名的“十三翼之战”。泰赤乌氏虽胜，但“内无统纪”，那颜们互争权力，对部众十分残暴，“攘其车马，夺其饮食”，而铁木真则极力笼络人心，厚待部民，因此照烈、兀鲁、忙兀等尼鲁温蒙古部落都脱离泰赤乌氏，归附铁木真。

　　1196 年，塔塔儿部叛金，金章宗命丞相完颜襄统兵讨伐，塔塔儿溃败，向斡里札河（今蒙古东方省乌勒吉河）逃奔。铁木真闻讯，即向脱里汗报告，于是脱里率领克烈军，铁木真以“为父祖复仇”的名义征集蒙古部军相从，进至斡里札河，攻破塔塔儿堡寨，获其首领，“尽掳其车马粮饷”。完颜襄以他们助征叛部有功，承制授与脱里王号，自此称王罕；授铁木真“札兀惕忽里”（ja’ut-quri，诸乣统领）官号。斡里札之战和金朝的封赏，大大提高了铁木真的威望和权力。从此他可以用中原王朝任命的部族长官身份统辖部众，号令诸家贵族了。回军后，他就以违背结盟誓约，不肯出兵为父祖复仇，还乘机偷袭他的老营等理由，击灭乞颜氏长支贵族主儿乞氏，夺取其部民，从而消除了联盟内最有资格与他争夺权位的一家势力。

　　1200 年，铁木真会同王罕进攻泰赤乌，败之于斡难河北，杀塔儿忽台。

　　接着又随从王罕进兵呼伦贝尔草原，攻打合答斤、散只兀、朵儿边、塔塔儿、弘吉剌等部，大掠其部民、牲畜。1201 年，札木合纠集泰赤乌氏残部和上述呼伦贝尔地区诸部贵族。结成一个松散的联盟，共推札木合为“古儿罕”（gur-qan，众汗之汗），谋攻铁木真。铁木真得到报告，起兵迎敌，战于海剌儿河（海拉尔河）支流帖尼火鲁罕之地，击溃札木合联盟。1202 年春，进攻答兰涅木儿格思之地（在今贝尔湖南）的塔塔儿部落，灭之。秋，他与王罕又共同击败了乃蛮不欲鲁罕的进攻。在攻打塔塔儿之前，铁木真发布了两条命令（札撒，Jasaq），一是战胜时不许贪财，事定后均分所得财物；二是战斗中兵马退动至原排阵处要返回力战（防止冲乱本军阵脚），违者斩。这实际上就是规定了任何人都要服从他统一军令，战利品应当由他统一分配，论功行赏。这是铁木真就任联盟首领后的第一次立法，其意义在于提高汗权，限制各家贵族。果然，按弹、火察儿、答里台斡赤斤等乞颜贵族不遵命令，按老规矩随意抢掠，被他派那可儿责罚，没收其所得财物分配给众军。长期以来，铁木真一直臣事王罕，追随他东征西讨，巧妙地依托着克烈的势力来壮大自己，一一清除了蒙古部内的敌对贵族，消灭了东部地区各强大部落。铁木真的势力日益壮大，引起王罕及其子亦剌合鲜昆的疑忌，札木合、按弹等蒙古部贵族也力劝王罕除掉他。以前铁木真曾为长子术赤向亦剌合之女求婚遭到拒绝，1203 年春，王罕父子计议伪许婚约，邀铁木真来饮“布① 关于十三翼之战的结局，《史集》和《圣武亲征录》都说铁木真获胜，但《元朝秘史》却记载他被迫退入斡难河的哲列涅狭地。后者较近真实。

　　浑察儿”（buquljar，定婚宴），乘机谋害，铁木真得到按弹弟也客扯连的家奴巴歹和启昔礼的密报，慌忙整军备战。王罕谋泄，发兵来攻，双方战于合兰真沙陀之地（当在今内蒙古东乌珠穆沁旗北境），铁木真虽经反复苦战，终因寡不敌众，退到哈拉哈河旁的建忒该山整顿败散军马，仅得四千六百骑，然后转移到班朱泥河（当在克鲁伦河下游之南）休整。当时他处境极为艰难，至射野马为食，汲浑水以饮。遂与追随他的忠实那可儿们宣誓：“使我克定大业，当与诸人同甘苦。苟渝此言，有如河水。”（《元史·扎八儿火者传》）后来，“同饮班朱泥河水”作为成吉思汗艰苦创业的佳话载入史册。

　　王罕获胜后，愈益骄傲轻敌。其部下蒙古贵族札木合等密谋杀他，被发觉，即逃奔乃蛮。铁木真元气渐复，探知王罕在折折运都山正搭起金帐，宴饮欢娱，毫无防备，于是率军偷袭，围攻王罕营帐，经过三天三夜激战，击溃其主力，王罕狼狈西逃入乃蛮部境，被乃蛮边将所杀。亦剌合逃到西夏，被逐，又辗转至曲先（今新疆库车）之地，亦被当地人所杀。克烈部众尽被铁木真所并。至此他完全征服了东起大兴安岭、西至杭爱山的所有部落，“帝业”基本上奠定了。

　　克烈的灭亡震惊了乃蛮部统治者，1204 年，自恃强大的太阳罕决定出兵攻打蒙古，并遣使连结漠南的汪古部，但汪古部首领阿剌兀思剔吉忽里却将乃蛮使者缚送铁木真。铁木真得到汪古部的报告，立即议定对策，将军马集中在哈拉哈河旁进行了整顿，按千户、百户、十户统一编组，委派了各级那颜，并建立了一支护卫军。然后率军逆克鲁伦河西进，布阵于萨里川（在克鲁伦河与土拉河两河上游之间）。太阳罕除率领乃蛮本部军外，又收罗了札木合等一批蒙古、克烈败散的贵族，蔑儿乞部首领脱脱，斡亦剌部首领忽都合别乞亦领兵来助，兵力甚多，但军纪涣散，内部矛盾重重，太阳罕又懦弱无能。当乃蛮军进至鄂尔浑河之东的纳忽昆山时，蒙古军亦至，札木合等见铁木真军容甚盛，麾下“四骏”（博尔忽、博尔术、木华黎、赤老温）、“四狗”（速不台、哲别、者勒篾、忽必来）骁勇无比，知难以取胜，即离太阳罕散去。乃蛮军大败，太阳罕受伤被擒，不久死；其子屈出律率残部西逃，投奔其叔不欲鲁罕。铁木真乘胜进兵至阿勒台山，征服了乃蛮部。札木合逃亡到倘鲁山（今唐努山），被跟随他的五个那可儿捕送铁木真处死。