也速该之死为忌恨他的势力的泰赤乌部提供了一个反目的机会。他们夺走乞颜部的部众，撇下铁木真母子而去。也速该寡妻带领几个孩子和少数忠实部民，在不儿罕山过了好几年艰难的日子，元气稍有恢复。这一家“莫不似飞禽的雏儿般毛羽长了；走兽的羔儿般大了”？泰赤乌部对此十分警惕，带人来攻，抓走了铁木真。多亏泰赤乌部的属民琐儿罕失剌的暗中相助，铁木真得从泰赤乌部逃脱。
经过这次危难，铁木真开始通过两种手段加紧扩展自己的势力。一是寻找和吸引渴望冒险、成功的年轻战士，与他们建立用个人效忠的誓约来约束的首领—那可儿（“伴当”，即伙伴、战友）关系，逐渐形成属于他个人支配的中坚力量。二是凭依着父亲也速该与克烈部首领王汗互为安答（即契交）的关系，他带着妻子从前“上见公姑的礼物”即黑貂鼠袄子，去主动投附王汗。他的策略很快发生了效用。不久，他遭到篾儿乞部的袭击，被迫仓促撤退；他妻子找不到坐骑，也被篾儿乞人俘虏去。王汗闻讯，不但自己派军队来帮助他，还促成蒙古札答阑氏出兵相救。篾儿乞人在不兀刺川（今译布拉河，在蒙古国北部）的老营被捣袭，铁木真夺回了妻子；他的长子术赤就出生在这次动乱之后，所以他的血统一直被认为十分可疑。
对篾儿乞部的复仇之战成为铁木真一生事业的重大转折点。以强大的克烈部和札答阑氏蒙古作为后盾，再加上他日益展露的个人魅力，他身边很快聚集起一批以渴望战功和崇拜英雄的那可儿为核心的私属部众，以及带着多少不等的部落民来与他结盟的乞颜部旧贵族。1180年代末，铁木真被推举为蒙古乞颜氏的首领。自也速该死后被泰赤乌人拆散，乞颜部经过近20年波折，终于在铁木真手里重新团聚在怯绿连河上游，形成漠北一支独立政治势力。
乞颜部的复兴引起泰赤乌氏和札木合的强烈敌意，他们联合起兵3万偷袭铁木真。铁木真获悉后整顿军马迎战。于是在怯绿连河上游某个沼泽地区发生了著名的“十三翼之战”。这场会战的得名，是因为双方兵马都组成十三个圈子。《史集》说，“在古时候，当某部落屯驻在某地时，就围成一个圈子。部落首领处于像中心点那样的圈子中央。这就称做古列延。……当敌军临近时，他们也按这种形式布阵。”交战结果很可能是铁木真处于劣势，他被迫后撤。他的第十三翼主力是从泰赤乌氏投奔他的赤那思部，在被札木合围捕后遭到严厉报复，札木合下令“将赤那思地面有的大王每。教七十锅都煮了”。
1196年，金朝出兵进攻塔塔儿部。塔塔儿在怯绿连河被金军打败，逆斡里札河（今译乌勒吉河，在蒙古国东北）奔命。铁木真获得塔塔儿部在金军追逼下“带着头口、茶饭”西向退却的消息，立即遣人报告王汗说：“他（指塔塔儿）正是废了我父祖的仇家。父亲可以助我夹攻。”王汗遂亲自领兵与铁木真会合，顺斡里札河东进，与金军夹攻倾巢出逃的塔塔儿人。经此一战，铁木真不仅给予他东面的劲敌以沉重的打击，而且因为主动配合金军作战被授以“札兀惕忽里”（即“幺军统领”，幺军是辽、金王朝在边疆地区组织的部族军队）的官职。金王朝在漠北部落中享有很高的威望。接受金朝的官职，有效地加强了铁木真号令诸部的政治权威。接着他就趁征讨塔塔儿新胜之势，回过头来引兵擒拿乞颜部内最桀傲不驯的长支贵族主儿乞氏。铁木真当众谴责他的阶下之囚背弃从前的盟誓，问他们：“你在前与我说甚么来？”两人说：“俺自说的言语不曾依。”遂伸颈就戮。主儿乞氏部众是当年合不勒汗从属民中专门挑选出来授与长子的“有胆量、有气力、刚勇能射弓的”百姓。这支“无人能敌”的游牧军队从此变成铁木真的“梯己百姓”。
随着乞颜部日渐兵强马壮和铁木真政治声望的不断提高，与泰赤乌氏一决雌雄的时机终于成熟了。1200年，铁木真与王汗会合，出攻泰赤乌部。双方在斡难河畔交锋。泰赤乌北退月良兀秃剌思之野（在今俄罗斯赤塔南鄂良古依河流域）。铁木真追至其地，再战。泰赤乌部众溃散，其首领西遁。
塔塔儿和泰赤乌相继溃败，使驻牧于呼伦贝尔地区的蒙古各部直接感受到乞颜部的威胁，于是居于草原东方的这些部落与塔塔儿残部会盟阿雷泉（在今海拉尔河下游），谋袭铁木真。铁木真闻讯，与王汗东进至捕鱼儿海子，将其击败。翌年，诸部又与塔塔儿、泰赤乌等被打散的贵族一起，在犍河（额尔古纳河支流，今译根河）边聚会，共推札木合为“古儿罕”（意即普上的汗），联合对抗铁木真与王汗的联盟。尽管他们口头上指天发誓，营造出一种“举足蹋岸，挥刀斫林”的壮烈气氛，实际上却是一班心中各怀私计的苟合之众。札木合率领着拼凑的兵马才动身，他的阵营里就有人设法给铁木真报信。铁木真遂领军相逆，在海剌儿河（今译海拉尔河）畔击溃札木合所部。乞颜氏的姻亲部落蒙古翁吉刺氏（迭列列斤蒙古）投降铁木真。
1202年秋天，早先被铁木真击溃的篾儿乞首领邀约草原西部大国乃蛮部的不亦鲁汗进击铁木真和王汗。前一年在海剌儿河之役战败后作鸟兽散的东方各部也卷土重来。这时铁木真和王汗正在呼伦贝尔草原之南、大兴安岭西麓休整人马，于是隐蔽辎重，在靠近金边墙处倚险据守，以逸待劳。乃蛮、札木合联军追踪而来，双方对峙于一个名叫阙奕坛的地方（阙奕坛系蒙语，意即“冷”。该地应在今哈拉哈河上源地区）。史称札木合令部下用巫术招唤风雪，“不意风雨逆回，天地晦暗”，反而朝自己的方向刮来。乃蛮方面军心大乱，以为“天不护韦占，所以如此”，乃溃散而去。东、西部草原联合对抗蒙古乞颜氏与克烈部联盟的战线，不经一击便顷刻瓦解。
自从铁木真曲意攀结王汗以后，一直称后者“汗父”。随着他的实力越来越强，王汗开始对这个“自的孩儿”暗怀疑惧。做过几天“古儿汗”的札木合，现在也去投靠王汗并竭力拉拢王汗的亲子桑昆，企图离间克烈和蒙古乞颜部的关系，从中渔利。受札木合唆使后力主与铁木真决裂的桑昆对父亲说：“你如今见存，他俺行不当数（意即他就不拿我作数）。汗父你教白的呛着、黑的噎着呵（意即若父亲你一日故去），将俺祖父辛苦着收集的百姓，如何肯教我管？”1202年春，优柔寡断的王汗在半信半疑间，勉强同意借议亲诱铁木真赴宴，把他捉获。谋泄，不得已先发制人，往攻铁木真。
铁木真来不及作充分的战争动员，被迫仓促应战。双方交锋于合兰真沙陀（当即今内蒙东乌珠穆沁旗北境的“额里彦沙陀”）。铁木真以劣势苦战不支，队伍溃败，结果只带了19人逃窜，退至哈勒哈河（今译哈拉哈河），检点陆续会集的残部，也只有4600骑。跟着铁木真落荒奔命的一群人，在班朱泥河（班朱泥意为沼泽）边饮浑水止渴。“同饮班朱泥水”成为铁木真艰难创业的一段最有代表性的故事。
合兰真沙陀之战并没有真正摧毁铁木真的实力。但反复无常的札木合自以为已经得逞，于是又挑起王汗阵营的内讧，想夺取王汗的部众。事情败露后，札木合被迫投奔乃蛮。至秋，铁木真经过休整，带重兵日夜兼行，偷袭王汗。他成功地将王汗的大营秘密包围起来，然后发动进攻。战斗持续了三天三夜。克烈部被铁木真全部征服。逃入乃蛮边境的王汗，被乃蛮边将杀死。被俘虏的全部克烈百姓，都在铁木真的部众中被“各各分了”。
古代风景画鉴赏战胜王汗使铁木真成为中部和东部草原最强盛的游牧领袖。但从辽代以来久盛不衰的乃蛮人却不把他放在眼里。乃蛮国王塔阳汗说：“这东边有些达达……看来他敢要做皇帝么道。天上只有一个日月，地上如何有两个主人？如今咱去将那达达取了！”为了“要将他每的弓箭夺来”，1204年初春，塔阳汗亲自领兵东趋。札木合纠合的泰赤乌等残部也余勇再贾，参加征讨。
正在帖麦该平川（今在大兴安岭中）围猎的铁木真，就围猎处与部属商量。众人多说马瘦，不主张迎战。斡赤斤（铁木真幼弟）说：“您如何推辞马瘦？我的马却肥！既听了这等说，如何坐得住？”别勒古台（铁木真异母弟）接着说：“若生时被人将弓箭夺了呵，济甚事！男子死呵，与弓箭一处岂不好？如今乃蛮恃其国大民众，敢发大言。我可趁此夺他弓箭又何难？”铁木真遂回到哈剌哈河边点视人马，按十户、百户、千户的十进位制统一组编人马，成立由1000多亲信勇士组成的亲卫军。然后率领新整编的军队溯怯绿连河而上，在萨里平川（今在克鲁伦河和土拉河二水上游之间）布设疑兵。至夜，令人各烧火五处。乃蛮前哨报告塔阳汗说：“达达军马塞满了萨里平川的地面。”塔阳汗斗志已经动摇，很想领兵回撤，诱敌深入，促其马瘦人乏，再找机会与之决战。但他的儿子却轻蔑地讥评道：“那妇人塔阳又是怕了！”塔阳汗被儿子激怒，于是决意东渡斡儿浑河驻营。札木合眼看恶战已经难以避免，又一次临阵脱逃。乃蛮军法衰弛，交锋一天后就军心瓦解，纷纷乘夜弃营出逃。到第二天，铁木真就完全击败乃蛮人。塔阳汗死于重伤。铁木真乘胜进至阿勒泰山地区。将塔阳汗属众尽行收捕。塔阳汗的母后曾骂蒙古人是“歹气息，衣服黑暗”。铁木真现在得意地问她：“你说达达歹气息。你却如何来？”于是将她纳为诸妻。札木合虽然又一次遁脱，但追随他的大部分东部草原氏族贵族，其中许多人与铁木真同属蒙古部，“全都在这次战争后屈服了，俯伏在铁木真脚下”。
大蒙古国的建立
乃蛮塔阳汗部败亡后，铁木真可以说已经处于漠北无对手的地位，剩下的不过是草原周边一些较弱小的部落，以及少数不止一次被他打败，但仍多少有一点部众，所以还在负隅顽抗的破落贵族。铁木真用两年多时间最终平定了蒙古草原残存的对立势力。
札木合的被擒，事在1205年。他是被他的五个伴当（随从伙伴）出卖，缚送到铁木真处去的。铁木真似乎对这个早年的安答仍怀有念旧之情，倒是札木合在最后的时刻表现出旧式英雄的气概。他对铁木真说：
“咱年小做安答时，不可消化的饮食曾共吃，不可忘的言语曾共说。因为将咱离间，所以分离了。想起在前说的言语，自羞面不敢与安答相见。如今安答欲教我做伴。当做伴时不得做得伴：如今你将众百姓收了，大位子定了，无可做伴。你若不杀我呵，似衣领上虱、底衿（指垫褥）内刺一般，反使安答日间心不安、夜间睡不稳。你母聪明，你又俊杰，弟每有技能，伴当每豪强，又有73匹骟马。我自小亡了父母，又无兄弟，妻好说长话，伴当不中倚仗。为这般所以有天命的安答胜了。如今恩赐教快死呵，安答得心安。倘又教不出血死呵，我死后于你子孙行，永远护助也者！”
于是铁木真下令，用“不出血死”的行刑方法，处死札木合。那就是把受刑人的身体整个地用毡毯裹实，让马匹或者人力践踏，直到毯子里的人完全死去。这是古代蒙古人处死贵族时常用的方法。当时他们还禁止用割喉管放血的办法宰羊，而是先剖开羊的胸膛，把手伸进去紧压住羊的心脏，使羊血凝结在羊肉里。可能他们认为这样做会有利于被宰杀的对象死后重生，所以蒙古贵族都宁可忍耐受刑时的剧烈痛苦，“教不出血死”。