到自己幼年时结下的安答、扎答阑部的首领札木合，让他一起协同作战。他们三部在鄂嫩河畔会师，打败蔑儿乞人，重新夺回了孛儿帖，这是铁木真的第一次重大胜利。
但这时的孛儿帖已经怀孕了，在获救回来的路上，她生下了一个儿子，就是成吉思汗的长子术赤，但谁也不知道他究竟是铁木真的儿子，还是蔑儿乞人的孩子。为了报复抢走自己生母的蔑儿乞人，别里古台射死了所有他能见到的蔑儿乞男人，而铁木真在这一仗里从蔑儿乞部夺到了许多奴隶和牲畜，壮大了自己的力量。为了表达对札木合的感激，他们再一次结拜成为安答，当脱斡邻带领着自己的部众回去以后，他继续留在了札木合部。
札木合的部众里有一些当年也速该的旧部，也速该死后他们投奔到这里，而现在，当铁木真住下以后，这些部众渐渐又都回到了他的身边。出于政治策略的需要和对当年情境的充分理解，铁木真完全不计较这些人曾经在自己和母亲最困难的时候离开，仍然热情地欢迎了他们。札木合也发现了铁木真势力的日渐壮大，他对于铁木真暗中争取自己部众的行为感到非常不满，言语中也流露出了这种情绪。铁木真觉察到札木合的戒心，就在一个夜晚带着部众悄悄离开了，札木合部中的许多也速该旧部也跟着他一起离开。
现在铁木真的部众已经被他管理得井井有条。这种富有秩序的组织形式使他们总能获得更多的猎物，而当一些被饥饿困扰的部落和人们希望获得帮助时，他又会慷慨相助，送给他们的食物数量经常超出他们事先的想象。于是铁木真不计前嫌和慷慨慈悲的名声不胫而走，前来归附的人越来越多。在后来的一段时间里，许多昔日的乞颜氏贵族和部众回到了铁木真身边。他们推举铁木真为首领，重新结成了乞颜氏贵族联盟。铁木真当选为汗的消息被报告到克烈部，脱斡邻也非常高兴。在他的支持下，铁木真重建部族的事业进行得非常顺利。他把自己的护卫组织和管理组织分给弟弟和亲信侍卫（即那可儿）们去领管，把自己的部众建设成了一支勇猛善战的队伍。
与札木合的纠葛
而在扎答阑部那边，自从铁木真离开札木合，建立起自己的势力以后，札木合觉得这个安答迟早要威胁到自己的地位，对他越发敌视。事实也的确如此，与铁木真相比起来，札木合的出身不够高贵，行为举止也不像他那样宽厚谦虚却富有气派，虽然札木合也有过人的才能，但为人却显得过于狠辣无情，经常会作出些损害盟友和下属的事情，让人们对他无法信任，转而投向铁木真的麾下。
恰好这时札木合的弟弟抢掠铁木真的马群，结果被铁木真的手下射死，札木合借这个机会联合了泰赤乌部等十三个部落，集结了三万大军向铁木真攻来。幸好札木合处有人向铁木真通报了消息，铁木真也及时准备，把自己的三万部众组成十三个古列延（即营地），他自己和母亲相额伦各统一营，其他的分别由本部和其他部的贵族统率，两军在鄂嫩河附近相遇，一场激战之后，铁木真败退，暂时到斡难河上游一带躲避，札木合带着铁木真的一些部众大胜而回，这就是著名的十三翼之战。但札木合在得胜之后，用七十口大锅煮死了俘虏，这种残暴的行为激起了许多人的不满，他们纷纷离开札木合，转而投向铁木真。所以铁木真部虽然在战斗中受到了损失，实力与名望却没有受到实质的损失。
公元1195年，塔塔儿部侵扰金朝边境。金朝出兵攻打，塔塔儿部败逃。得到这个消息，铁木真感到为父亲报仇的机会来了，他与脱斡邻联络，联合出兵截击，大败塔塔儿部。这一次铁木真不但为父亲报了仇，缴获了大量物资，还得到了金朝的封赏，被封为“札兀惕忽里”，意思就是统领诸部落。虽然这只是对铁木真已有地位的承认，但毕竟是得到了金朝的正式认同，铁木真因此进一步巩固了地位。脱斡邻也被封为王，从此以后人们就都称他为“王罕”。铁木真把劫掠来的东西都送给了王罕，继续和他保持友好的关系。
虽然铁木真的势力壮大了不少，但距离成功还差得很远，草原上还有许多部落与他为敌。公元1201年，札木合联合了泰赤乌部、蔑儿乞部、塔塔儿部和西方的斡亦剌部、乃蛮部等部落，组成联军共同去袭击铁木真…王罕联盟。但后者的实力毕竟很强大，而且在札木合联盟行动的前夕，他下属的部落里却有人跑去把这个消息告诉铁木真，让他们提早做好了准备。铁木真这一生中经常遇到类似的事情，一到危难来临时就有人向他通风报信，由此也可以看出他确实有很好的名望，才能赢得来自敌对阵营里的支持。
铁木真与札木合的战斗开始后天气突变，骤起的狂风卷着雨雪向札木合的军队扑去，士兵们一霎时感到天昏地暗，许多人马在逃跑时掉进了山涧，许多人自相践踏而死，还有许多人被冻僵了，躺在地上动弹不得。札木合带着部众向额尔古纳河逃去，但此时他又暴露了自己性情中最恶劣的一面，竟然对同盟军的部落大加抢掠，从此彻底声名扫地，失去了最后的支持者，再也不能以自己的力量与铁木真为敌了。
铁木真与王罕分别追击敌军的残余部队。王罕在往额尔古纳河的路上收降了许多札木合的部众，铁木真则去攻打泰赤乌部，终于在鄂嫩河把他们消灭。铁木真小时候的对头塔儿忽台现在仍是泰赤乌部的首领，在逃跑的路上，他的仆人纳牙阿父子三人打算抓了他去送给铁木真，但纳牙阿早就听说过铁木真最痛恨背信弃义的人，猜想如果他看到自己抓了主人来请功，一定会把他们杀掉，于是就放掉了塔儿忽台，空手去投奔铁木真。果然不出所料，铁木真听了事情的经过以后，称赞说：
“你们做得很对。如果真抓了自己的首领来投奔我，我一定会把你们都给杀了！”
消灭泰赤乌人以后，铁木真又乘胜进军，消灭了塔塔儿部。为了报仇，他准备杀死所有的塔塔儿男子，但他的弟弟别里古台却不慎泄露了这个计划，使得塔塔儿人拼死抵抗，让前来屠杀他们的蒙古人遭受了很大伤亡。别里古台因此受到铁木真的严厉处罚，不许他再参加亲族机密会议。
在这场战役中，部落里的贵族阿勒坛、忽察儿和答里台违反军令，自行掠夺财物。他们本以为自己是贵族，不会受到军纪的制约，但铁木真却觉得越是近亲越应该严加约束，否则人人效仿，不但自己的威信荡然无存，还会让贵族们心生傲慢，总有一天会走上叛逆的道路。于是他没收了这些人掠来的财物马匹，这三个人感到很不满，就转而去克烈部投奔王罕。
与王罕和札木合的决战
经过长时间的合作以后，铁木真和王罕之间的矛盾也越来越深。王罕拥有强大的实力，但能力却比铁木真差得远，他缺乏决断和远见，容易被别人的意见左右，而且对利益看得太重。铁木真曾经帮他对付夺位的弟弟，不但救了他的命，帮他恢复汗位，还送给他大量战利品，而王罕在胜利后却把战利品全部据为己有，还曾经在联合军事行动中抛下铁木真的队伍独自离开，让铁木真陷入危险的境地。面对铁木真一次次无私的相救，他也曾经愧悔交织，认铁木真为养子，并要在去世之后让他做自己的继承人，但在亲生儿子桑昆等人的挑拨离间下，他又时常会动摇，怀疑起铁木真的诚意。札木合和阿勒坛等人被王罕收留后，更是一再挑起王罕父子对铁木真的仇恨，说等到王罕去世后，铁木真一定会夺取克烈部的汗位。在这种意见左右下，桑昆决然拒绝了铁木真为儿子术赤的求婚，让铁木真的自尊心很受打击。
1203年，桑昆打算发动突然袭击除掉铁木真，但又有人把这个消息连夜赶去报信，而札木合也希望看到他和王罕拼个两败俱伤，就把克烈部的部署和进攻计划详细地转告给他。铁木真连忙准备迎战，但终因寡不敌众，受了很大损失，只能败退到班朱泥河一带休整。当时他手下的人马几乎损耗殆尽，处境极为艰难，以至于食野马、饮浑水，但他并不气馁，在水边与同伴们向天发誓：“如果我能克定大业，当与大家同甘苦。如负此言，有如河水！”他在这里立足下来，派人去问王罕为什么要这样对待他。在使者陈述的一连串的事实面前，王罕也感到很愧疚，对铁木真的态度又出现了动摇。
过了不久，札木合和阿勒坛、忽察儿打算谋取王罕的汗位，王罕发觉了他们的阴谋，这些人只好率部众投奔乃蛮部，而铁木真的叔叔答里台却为背叛了侄子而后悔，又回头去投奔铁木真了。王罕的势力因此而被削弱。到了秋天，铁木真已经重新恢复了元气，他了解到克烈部中发生的一切，就趁着王罕正在举行宴会，毫无防备的时机，率军围攻王罕的营帐。经过连续三昼夜的激战，王罕的主力军队全被消灭，克烈部被铁木真吞并，王罕西逃进乃蛮境内，被乃蛮边将杀死，他的儿子也在逃亡的路上被杀。到这时，铁木真已经完全征服了东到大兴安岭、西至杭爱山之间的所有部落，成了草原上的新霸主。
当时西边的乃蛮部也被铁木真惊动了。公元1204年，乃蛮部首领太阳汗决定联合漠南的汪古部出兵攻打蒙古，但汪古部的首领却把这个消息告诉了铁木真。铁木真立即和将领们议定对策，率领大军由克鲁伦河向乃蛮部进发。两军在纳忽山崖相遇，札木合等人看到铁木真的将士勇武，队伍严整，知道乃蛮部肯定不能取胜，就先行散去。太阳汗一向懦弱而又自大，他的军队并不是铁木真的对手，很快就被杀得大败，许多士兵坠崖而死，太阳汗本人受重伤身亡，他的儿子屈出律逃走，札木合也被跟随他的五个那可儿送到铁木真处。铁木真还顾念当年的友谊，想要与札木合修好，但札木合拒绝了他的要求，只希望不流血而死。铁木真满足了他的愿望，又把出卖札木合的五个随从作为叛徒处死。
就这样，蒙古高原上的所有部落都被铁木真征服，纷争的日子走到了尽头，成吉思汗的时代即将开始了。
成吉思汗
公元1206年，铁木真在斡难河源头举行大聚会，正式即帝位。巫师阔阔出在会上宣布了上天的旨意，说铁木真应该得到“成吉思汗”的尊号。关于“成吉思”的意思，有人认为是突厥语“大海”，意即大海一样伟大的皇帝，也有人认为应当是古突厥语“可怕的”、“强健的”，这种说法似乎更加可信。成吉思汗把自己的部落名称“蒙古”用作国号，即为大蒙古国。从此以后，当年分散在各部落的人们逐渐融合起来，成为一个共同的蒙古民族。
随后成吉思汗建立起了蒙古国的统治制度。国家的最高权力必须集中于汗，整个蒙古只能有一个在位的君王，一个汗。当汗去世之后，下一个即位的汗要经过贵族议会的推举，他必须也是成吉思汗的后裔。在大封功臣时，成吉思汗不但给每个人以丰厚的赏赐，还在封赏前回忆他们共同经历的征战岁月，当众列出他们的功绩和对自己的忠心，对他们极力赞扬。部将们感念成吉思汗对他们的情义，对他更加钦佩忠诚。
成吉思汗把全蒙古的部众分成了九十五个千户，分别分配给八十八个开国功臣。虽然名为千户，其实它们的规模大小不一，有的实际管理着几千户，有的则还不满一千户。千户体制既是军事单位也是行政单位，完全取代了过去的氏族部落组织。所有的百姓都被划进相应的千户里，他们必须在指定的牧地范围里放牧，不能擅离所部。在千户之上，成吉思汗又设了左右翼两个万户，博尔术为右翼万户，管辖西边直至阿尔泰山的各千户，木华黎为左翼万户，管辖东边直到大兴安岭的各千户。在千户以下，又有百户和十户的组织单位。
这种千户制度完全瓦解了原有的氏族部落形式，把军事单位和行政单位融为一体，让每个蒙古人都成为蒙古国的臣民，彻底消除了氏族贵族复辟的可能。
第二项是怯薛机构。这支机构是大汗的护卫军，它有严格的选拔制度，从一层层贵族子弟中选拔出来，同时具有笼络人质的作用。这是由大汗直接掌握的最精锐的部队，担任四怯薛之长的是成吉思汗最亲信的那可儿博尔忽、博尔术、木华黎、赤老温四家子弟，世袭承继。作为大汗的侍从近臣，怯薛不仅是大汗的亲卫军，有时也要处理王室的各种事务，在大蒙古国的军政事务中发挥了作用。
第三项是大断事官的设置。�