此后，铁木真挥军向塔塔儿进攻，一举将敌人击溃。溃军西逃，铁木真又穷追至兀鲁回失连真河（在今东乌珠穆沁旗境内），杀死了他们首领，掠获了大批塔塔儿人。然而在战斗中仍然发生了严重的违纪事件。违纪的是以前推举铁木真为汗的乞颜氏贵族阿勒坛（忽图剌汗之子、铁木真的堂叔）、答里台斡赤斤（铁木真的亲叔）、忽察儿（捏坤太子之子、铁木真的堂兄）三人。他们依仗亲贵和辈分比铁木真高的身份，未等分配战利品，便开始抢夺财物据为已有。
为了维护汗权的尊严，做到令行禁止，铁木真派哲别、忽必来二人毫不客气地没收了他们抢获的财物。答里台斡赤斤三人为此心怀不满，不久便脱离铁木真，投往王罕一边，并且参与攻击铁木真的行动。
然而铁木真这次巩固汗权，制裁旧贵族的果断措施，为提高军队的战斗力，最终取得统一高原的胜利，发挥了十分重要的作用。
征服了塔塔儿之后，铁木真在一个大帐房里召集乞颜氏贵族开会，商议如何处置塔塔儿部众。最后，他们决定把他们像车轴高的男人，不用问就杀死，把余下的妇女和儿童，分给各家，当作守门的奴隶！
被俘的塔塔儿人知道他们将面临像车轴高的男人都被杀死的厄运，便在大屠杀开始之前，每个人都袖藏一把利刀，到时与进行屠杀的人展开了殊死的搏斗，使铁木真的军队再次遭到极大的损失。
塔塔儿的被消灭，标志着东部蒙古各部已被铁木真征服。这对于他日后向高原的中部和西部扩展十分有利，他可以没有后顾之忧地进攻或者后退，不必担心来自东西部敌对势力的两面夹击。
消灭克烈部
在征服塔塔儿后，铁木真的劲敌就剩下西部蒙古各部了，而西部蒙古各部中实力最强大就是克烈部，其实力也在铁木真之上。但面对铁木真无人可挡的锋芒，王罕也紧张起来，加上逃亡的札木合的挑拨，王罕决定先发制人，对铁木真发动袭击。
但是，由于王罕部下的两个牧民透露了消息，铁木真已做好了战斗的准备。王罕的攻击没有摧垮铁木真，反使他的儿子桑昆受了箭伤。
然而，王罕毕竟兵多将广，实力雄厚，铁木真是经不起这种消耗战的，因而不得不把部队撤走，并派人向王罕求和。
失败的铁木真在艰难中收集部众，同时苦苦地等待时机。很快运气站在了他这一边。王罕在1203年春击败铁木真之后，他志骄气盛，竟然忘乎所以了，同金朝发生了冲突。金朝派军队征讨王罕，王罕大败溃逃，元气大伤，这样他最后失败的厄运也就很快降临了。铁木真看准了这个时机，准备在这一年的秋天突袭王罕。
铁木真决定在实施突袭王罕之前，使用诈降术。他以合撤儿的名义向王罕派出使者，使者是合撤儿的部下照烈部人。王罕早就知道这两名使者是跟随合撒儿的人，因此对他们的话深信不疑。他十分赞许使者说的话，很好地款待了他们，还派自己的亲信亦秃儿坚随他们一起去见合撒儿，以便双方结盟。
当铁木真发现王罕思想松懈、失去警惕时，他发动了突然袭击。
铁木真的军队连夜不停地驱马前进，逼近了王罕的住地。这时毫无戒备的王罕正搭起金帐，在里面宴饮，但轰轰的马蹄声惊醒了他的迷梦。
王罕的那可儿们顽强抵抗，战斗十分激烈，一直持续了三天三夜，最后克烈人战败投降。
王罕败逃，在鄂尔浑河畔被乃蛮人所杀。他的儿子桑昆一直逃到合失合儿（今新疆喀什），也被当地人杀了。
就这样，风云一时的王罕及其克烈部被消灭了，这使铁木真扫除了他统一高原的最大障碍。在整个统一蒙古高原的过程中，王罕曾屡克群雄，讨灭了不少大大小小的割据一方的部落，在这个意义上来说，他是有功业的。如今王罕的基业已为铁木真所有，他就此成为高原上最强大的势力，因此，对王罕作战的胜利是铁木真取得成功的关键之一。
击败乃蛮部落
克烈部败亡后，无处立身的札木合只好投奔到乃蛮人那里。乃蛮是一个文化发达、建立了政权的大部落，当时的统治者叫塔阳汗。塔阳汗得知克烈部被消灭、铁木真统一了大半个蒙古的消息后非常惶恐，加上札木合的挑拨，决定以铁木真为敌。他采取的对策是：南联汪古，上下夹击。但是汪古人不愿与铁木真结怨，反而把塔阳汗的计谋告诉了铁木真。铁木真知道这个消息后，知道与乃蛮的战争不可避免，于是一面通过中亚的商人摸清乃蛮的军队实力和部署，一面再次整顿自己的军队，以增强战斗力。他把自己的军队按十人、百人、千人组织起来，任命自己的亲信当百夫长和千夫长；设置“扯儿必”（把总）管理辊重；挑选精兵组成“怯薛”（护卫军）；又从精兵中挑选上千名勇士当前锋。这样一支机动灵活、配合协调的军队，是非常适应草原作战的需要的。
1204年夏，铁木真率领大军出征乃蛮。铁木真驻军于哈勒哈河畔的建忒该山；塔阳汗则扎营于杭爱山。当铁木真与手下众将领商量出征时，有人认为夏天马瘦，不宜行军，主张等到秋天时再出征。铁木真采纳了其弟别里古台的意见，认为正可利用乃蛮不备之机出兵，必获全胜。铁木真率军沿克鲁伦河前进，驻军萨里川。塔阳汗也率军渡过鄂尔浑河东进，双方在纳忽昆山相遇。摆好阵容后，恰巧铁木真军营中有一匹瘦马受惊逃入乃蛮营中。塔阳汗一看铁木真的马瘦成这样子，于是有轻敌之心。他亲自跃马索战，铁木真摆好阵势准备迎战。
这时跟随塔阳汗一起上阵的札木合，看到铁木真的军容十分整肃，简直今非昔比，知道交战后凶多吉少，就偷偷地溜走了。
这一天，战斗十分激烈、残酷。到下午时，塔阳汗的军队渐渐招架不住，塔阳汗也身负重伤被俘。此后形势开始急转直下，乃蛮军队顿时溃散，在黑夜中到处奔逃，坠崖身亡者不计其数，只有少数军队在塔阳汗的儿子屈出律率领下逃到西辽境内。不久塔阳汗因伤重死去。
这场大战后，乃蛮的百姓都成了铁木真的俘虏，追随塔阳汗的朵鲁班、塔塔儿、哈答斤、散只兀等部也纷纷投降了。
乃蛮战役的胜利使铁木真离完成统一全蒙古的事业越来越近了。
从此，铁木真的威名震动了蒙古高原，余下的一些尚未征服的部落都不是铁木真的对手，他们或被击破，或自动归附。
瓦解篾儿乞部
在铁木真与太阳汗激战的时候，篾儿乞首领脱脱和他的儿子们乘乱逃脱。铁木真在收服了乃蛮之后，立即率军追击，在合剌答勒忽札儿地方追及脱脱。脱脱拼死抵抗，终究还是不是铁木真的乘胜之师的对手。脱脱又退到萨里川，在那里再次被打败，大部分部众都成了铁木真的俘虏。脱脱带着儿子们和少数士兵逃往不欲鲁汗处，他和屈出律、不欲鲁汗的最后被讨灭，是在铁木真建国之后陆续进行的。
篾儿乞及其所属各支属民都被铁木真征服了，其中包括兀都亦惕篾儿乞、麦古丹、脱脱里、掌斤等部。脱脱之子忽秃的两个妻子秃该、脱列哥那也被捉获，铁木真将脱列哥那给了第三子窝阔台为妻，她就是史书上所说的乃马真氏六皇后，她生了贵由汗，在蒙古史上曾起过重大作用。
篾儿乞部的一个分支—一兀洼思篾儿乞的首领答亦儿兀孙看到大势已去，便带着自己的女儿忽阑去投降铁木真。铁木真对忽阑宠爱有加，让她做了自己的第二夫人，地位仅次于孛儿帖。
忽阑的父亲答亦儿兀孙降附铁木真后，向铁木真禀告说，他们因为没有驮用和骑用的牲畜，所以不能够随军出征。实际上他是准备伺机叛变。铁木真相信了他的话，便下令将答亦儿兀孙及其所属的兀洼思篾儿乞人划分为百户，并为他们设置了长官，让他们留在后方。可是当铁木真一离开，答亦儿兀孙便率领这些篾儿乞人发动了叛乱，抢夺了铁木真后方的辎重。留守后方的铁木真军队人数不多，他们集合起来，与答亦儿兀孙展开激战，将辎重夺回。答亦儿兀孙战败，带领残众逃到薛灵哥河（今色楞格河）地区的哈剌温隘筑寨居住下来。
铁木真闻讯，派博尔忽和锁儿罕失剌之子沉白率右翼军前去讨伐。
他们追到哈剌温隘，将躲在寨子里的兀洼思篾儿乞人全部擒获。铁木真将他们拆散，分配给蒙古人当奴隶。还有一批人数很多的篾儿乞人也乘机反叛了，他们跑到名叫台合勒山的寨子里，拒守抗命。铁木真又令沉白率左翼军前往镇压。沉白很快攻下寨子，将他们全部俘虏。
铁木真下令杀死一部分篾儿乞人，余下的也分配给蒙古人当了奴隶。长期与铁木真为敌的篾儿乞部终于势衰瓦解了，其首领脱脱的最后灭亡，只是时间问题。
统一全蒙古
蒙古高原各部落纷纷被铁木真降服之后，铁木真昔日的强敌只剩下札木合了。然而札木合的强盛已是昨日黄花，在王罕、太阳汗相继灭亡之后，他已惶惶然有如丧家之犬。在蒙古高原的早期部落中，札木合曾经是蒙古部最有实力的人物，铁木真也一度是他的附庸。在铁木真拉出一些部众，离开札木合独自发展势力之后，札木合纠集各部力量，与铁木真、王罕进行了长期的较量，然而一再失败。札木合失败后，先是投靠王罕，离间王罕与铁木真的关系，王罕灭亡后他又投奔太阳汗，太阳汗被铁木真击溃后，他的部众纷纷离他而去，只有五个那可儿跟随着他。
札木合和他的五个那可儿逃到傥鲁山（今唐努山），一贫如洗，便在那里做抢劫财物的盗贼，有的时候还需靠打猎为生。后来五个那可儿们把札木合捉了起来，送到铁木真处请降。
铁木真讨厌背叛自己主人的人，他当着札木合的面，将那五个那可儿杀掉了。对于札木合，铁木真犹念他是自己幼时的好友，在自己势力未张之时，也曾得到过他的援救，因此是杀是留，颇感犹豫。
但是札木合知道，草原上的英雄最终只能有一个，已经穷途末路的他即使活下去，也不会再有作为。他原本是一代枭雄，现在他决不甘心做仰人鼻息的阶下囚。因此他在向铁木真表达自己的感激之情的同时，也表示了自己的必死决心。
铁木真于是下令按处置贵族的方式，赐札木合不流血而死。采取这样的死刑，是因为蒙古人认为灵魂居于血液之中，不流血就保住了灵魂。
辽阔的蒙古高原绝大部分都已处在铁木真的统治之下了，到这时，铁木真才有了他自己的独立的可汗地位。他顺应统一的大势，艰苦创业，克敌制胜，终于取得了成功，下一步便是创建国家，并凭借新的政权，扫平高原上尚未降服的势力，再驱赶他的铁骑去征服更加广大无边的土地。
建立大蒙古国
1206年，全蒙古的奴隶主贵族们在鄂嫩河畔举行了大聚会，推举44岁的铁木真为全蒙古的大汗，并上尊号为成吉思汗。“成吉思”是蒙古语强大的意思。
成吉思汗建立大蒙古国之后，吸收以往游牧政权的经验，采取一系列措施，建立和完善了蒙古游牧国家的统治机构和制度。
在成吉思汗即位之后，他在其征服的所有蒙古部落中普遍推行千户制。除一些发展水平较低的林木中百姓之外，把全部蒙古国的百姓划分为95个千户，任命那些与成吉思汗一起建国的贵族、功臣为干户长，使他们世袭管领本千户百姓。千户下设百户、十户，设百户长、十户长管辖。
通过编组千户，全部蒙古百姓都被纳入严密的组织之中，所有民户都在所管千户内生活和供役，在指定的范围内居住和游牧，由大汗委任千户各级官吏，任何人不得檀离所属的那颜和千户、百户、十户，违者严惩。
另外，成吉思汗封了三个万户长作为军事统帅。命木华黎为左翼万户长，管辖从蒙古国中心向东直到哈利温山方面的诸千户；博尔术为右翼万户长，管辖从蒙古国中心西至阿勒台山的诸千户；纳牙阿为中军万户长，管理漠北中心地区的各千户。万户长本人也是一个干户之长。此外，又任命两个万户镇守西北地区，封豁儿赤为八邻万户之长，其地在阿勒台山北，镇守也儿的石河一带的林木中百姓。封忽难为万户长，管领成吉思汗长子术赤所属“林木中百姓”，约在今叶尼塞河上游一带。
此外，1206年，成吉思汗成为蒙古国最高君主后，原来的怯薛建制己不能适应其崇高的地位，为了确保大汗的权力，在原怯薛的制度上（八十宿卫、七十散班）基础上扩建了一支更强大的常备军，由大汗直接控制。成吉思汗把怯薛扩充为1万名，包括1000名宿卫、1000名箭筒士、8000名散班。选万户长、千户长、百户长、十户长等那颜及白身人子弟中有技能和身体健壮者充任。
成吉思汗建国前，蒙古人还没有普遍使用文字。成吉思汗灭乃蛮部时俘获其掌印官畏兀儿人塔塔统阿，命其以回鹊字母拼写蒙古语，创制蒙古文字，教授蒙古贵族子弟学习。从此，发布命令、登记户口、记录案件都使用回鹊式蒙古文。
成吉思汗通过采取以上几项措施，建立和完善了蒙古游牧国家。
而成吉思汗成为全蒙古的汗，也标志着蒙古族的历史进入了新的阶段。因为几个世纪来，蒙古各部从来没有统一过，他们互相残杀，纷争不已；现在，他们在强有力的领袖成吉思汗的统治下形成了统一的局面。在东至今大兴安岭，北至贝加尔湖，西至阿尔泰山，南至阴山的辽阔地域内，过去语言、民族、文化水平各有差异的各部落开始结合成一个共同体，他们之间文化和经济联系进一步加强，共同的语言逐步形成，勤劳勇敢的蒙古族开始了形成的过程。从此，伟大的蒙古族开始在中国和世界历史舞台上发挥巨大的作用。
成吉思汗成为全蒙古的汗，也标志着蒙古历史上第一个统一的政权——大蒙古国正式建立。
