自从铁木真曲意攀结王汗以后，一直称后者“汗父”。随着他的实力越来越强，王汗开始对这个“自的孩儿”暗怀疑惧。做过几天“古儿汗”的札木合，现在也去投靠王汗并竭力拉拢王汗的亲子桑昆，企图离间克烈和蒙古乞颜部的关系，从中渔利。受札木合唆使后力主与铁木真决裂的桑昆对父亲说：“你如今见存，他俺行不当数（意即他就不拿我作数）。汗父你教白的呛着、黑的噎着呵（意即若父亲你一日故去），将俺祖父辛苦着收集的百姓，如何肯教我管？”1202年春，优柔寡断的王汗在半信半疑间，勉强同意借议亲诱铁木真赴宴，把他捉获。谋泄，不得已先发制人，往攻铁木真。
铁木真来不及作充分的战争动员，被迫仓促应战。双方交锋于合兰真沙陀（当即今内蒙东乌珠穆沁旗北境的“额里彦沙陀”）。铁木真以劣势苦战不支，队伍溃败，结果只带了19人逃窜，退至哈勒哈河（今译哈拉哈河），检点陆续会集的残部，也只有4600骑。跟着铁木真落荒奔命的一群人，在班朱泥河（班朱泥意为沼泽）边饮浑水止渴。“同饮班朱泥水”成为铁木真艰难创业的一段最有代表性的故事。
合兰真沙陀之战并没有真正摧毁铁木真的实力。但反复无常的札木合自以为已经得逞，于是又挑起王汗阵营的内讧，想夺取王汗的部众。事情败露后，札木合被迫投奔乃蛮。至秋，铁木真经过休整，带重兵日夜兼行，偷袭王汗。他成功地将王汗的大营秘密包围起来，然后发动进攻。战斗持续了三天三夜。克烈部被铁木真全部征服。逃入乃蛮边境的王汗，被乃蛮边将杀死。被俘虏的全部克烈百姓，都在铁木真的部众中被“各各分了”。
古代风景画鉴赏战胜王汗使铁木真成为中部和东部草原最强盛的游牧领袖。但从辽代以来久盛不衰的乃蛮人却不把他放在眼里。乃蛮国王塔阳汗说：“这东边有些达达……看来他敢要做皇帝么道。天上只有一个日月，地上如何有两个主人？如今咱去将那达达取了！”为了“要将他每的弓箭夺来”，1204年初春，塔阳汗亲自领兵东趋。札木合纠合的泰赤乌等残部也余勇再贾，参加征讨。
正在帖麦该平川（今在大兴安岭中）围猎的铁木真，就围猎处与部属商量。众人多说马瘦，不主张迎战。斡赤斤（铁木真幼弟）说：“您如何推辞马瘦？我的马却肥！既听了这等说，如何坐得住？”别勒古台（铁木真异母弟）接着说：“若生时被人将弓箭夺了呵，济甚事！男子死呵，与弓箭一处岂不好？如今乃蛮恃其国大民众，敢发大言。我可趁此夺他弓箭又何难？”铁木真遂回到哈剌哈河边点视人马，按十户、百户、千户的十进位制统一组编人马，成立由1000多亲信勇士组成的亲卫军。然后率领新整编的军队溯怯绿连河而上，在萨里平川（今在克鲁伦河和土拉河二水上游之间）布设疑兵。至夜，令人各烧火五处。乃蛮前哨报告塔阳汗说：“达达军马塞满了萨里平川的地面。”塔阳汗斗志已经动摇，很想领兵回撤，诱敌深入，促其马瘦人乏，再找机会与之决战。但他的儿子却轻蔑地讥评道：“那妇人塔阳又是怕了！”塔阳汗被儿子激怒，于是决意东渡斡儿浑河驻营。札木合眼看恶战已经难以避免，又一次临阵脱逃。乃蛮军法衰弛，交锋一天后就军心瓦解，纷纷乘夜弃营出逃。到第二天，铁木真就完全击败乃蛮人。塔阳汗死于重伤。铁木真乘胜进至阿勒泰山地区。将塔阳汗属众尽行收捕。塔阳汗的母后曾骂蒙古人是“歹气息，衣服黑暗”。铁木真现在得意地问她：“你说达达歹气息。你却如何来？”于是将她纳为诸妻。札木合虽然又一次遁脱，但追随他的大部分东部草原氏族贵族，其中许多人与铁木真同属蒙古部，“全都在这次战争后屈服了，俯伏在铁木真脚下”。大蒙古国的建立乃蛮塔阳汗部败亡后，铁木真可以说已经处于漠北无对手的地位，剩下的不过是草原周边一些较弱小的部落，以及少数不止一次被他打败，但仍多少有一点部众，所以还在负隅顽抗的破落贵族。铁木真用两年多时间最终平定了蒙古草原残存的对立势力。
札木合的被擒，事在1205年。他是被他的五个伴当（随从伙伴）出卖，缚送到铁木真处去的。铁木真似乎对这个早年的安答仍怀有念旧之情，倒是札木合在最后的时刻表现出旧式英雄的气概。他对铁木真说：“咱年小做安答时，不可消化的饮食曾共吃，不可忘的言语曾共说。因为将咱离间，所以分离了。想起在前说的言语，自羞面不敢与安答相见。如今安答欲教我做伴。当做伴时不得做得伴：如今你将众百姓收了，大位子定了，无可做伴。你若不杀我呵，似衣领上虱、底衿（指垫褥）内刺一般，反使安答日间心不安、夜间睡不稳。你母聪明，你又俊杰，弟每有技能，伴当每豪强，又有73匹骟马。我自小亡了父母，又无兄弟，妻好说长话，伴当不中倚仗。为这般所以有天命的安答胜了。如今恩赐教快死呵，安答得心安。倘又教不出血死呵，我死后于你子孙行，永远护助也者！”
于是铁木真下令，用“不出血死”的行刑方法，处死札木合。那就是把受刑人的身体整个地用毡毯裹实，让马匹或者人力践踏，直到毯子里的人完全死去。这是古代蒙古人处死贵族时常用的方法。当时他们还禁止用割喉管放血的办法宰羊，而是先剖开羊的胸膛，把手伸进去紧压住羊的心脏，使羊血凝结在羊肉里。可能他们认为这样做会有利于被宰杀的对象死后重生，所以蒙古贵族都宁可忍耐受刑时的剧烈痛苦，“教不出血死”。
1206年丙寅，古代蒙古人按十二生肖纪年法称作“巴儿思只勒”即“虎儿年”，铁木真在斡难河头的祖先旧营地树起有九根牦牛尾装饰的幡帜，召集大聚会（蒙语quriltai，汉语译音为忽里台；今蒙古国批准立法和组织、监督政府的最高权力机构称为大“呼拉尔”，即源于此词），正式举行登上“大汗”宝座的仪式。
古代蒙古人信奉一种万物有灵论的原始巫教。他们崇拜的万事万物最高主宰是“长生天”（即永恒的天），同时也崇拜日月、山川、土地的神灵，崇拜火。能在活着的人与长生天、天上和冥间万神以及死去的祖先之间保持联系的巫师，当时称为“孛额”，在西方使用突厥语的蒙古人中也按突厥人的叫法称他们为“甘”（突厥语kam的音译）。孛额“骑白马，着白衣，坐在众人上面”，是草原上到处受人敬重的角色。当孛额与上天、各种自然神灵或死去的人们沟通的时候，经常会发生全身的痉挛、颤抖和狂乱的动作。人们通过他们向上天祈求保护，消除各种灾祸，增进幸福。因此传说中法力无边的男、女巫师本身也成了蒙古人崇拜的对象。他们用毛毡、丝绸制作成模拟他们的小偶像，放在帐幕里作为家庭的保护神。现在一般都把这种原始巫教叫做“萨满教”。其实“萨满”最初是女真—满洲人给予同类巫师的名称，13至14世纪的蒙古语中并没有使用这个词汇。
铁木真想称霸草原，当然需要神权的支持。尼伦蒙古部的巴邻氏贵族世代有孛额的身份，所以在铁木真的部众中有很高的地位。铁木真又选择迭列列斤蒙古部晃忽坛氏的蒙力克作自己的继父。蒙力克的诸子中有一人名阔阔出，也是一个有名的孛额，有“帖卜腾格里”的名号，意思是“真正天上的”。人们相信他经常在隆冬时裸坐在斡难—怯绿连最寒冷一处地方的冰上，用体温融化凝冰，然后乘升腾的蒸气，骑着白马上天去。阔阔出不断地向铁木真传达长生天的意志说：“神命你为普世的君主！”又说：“天神跟我谈过话。他说，‘我已把整个地面赐给铁木真及其子孙，命他为成吉思汗’。”
如今，按照长生天的意志作“普世的君主”的时机终于成熟了。就在1206年的大聚会上，铁木真称“成吉思汗”，登上了统治全体草原游牧民的“大位”。“成吉思”的字义，有人说是“伟大”的意思，有的说是来自他即位前五色吉祥鸟鸣叫的声音“青吉斯”，有人说是蒙语“坚强”、“有力”的意思。现代的学者则倾向于认为它是突厥语tengiz（译言“海洋”）一词的变音，是“海内的”（亦即普天下的）之意。
