挫折和灾难磨炼了铁木真的意志，他决心恢复父亲的事业。他懂得单凭自己的力量是不能战胜敌人的，只有利用蒙古各部之间的矛盾，取得一些部落主的支持，才能壮大自己的力量，打败敌人。
统一东部蒙古
铁木真和当时势力强大的王汗和札木合分别结为义父和兄弟，取得他们的支持。在他们的帮助下，铁木真开始恢复元气，许多旧时的部属又纷纷回来了。铁木真对部族进行了一些改革，加强了控制，把权力牢牢抓在自己手里。1189年，铁木真被拥戴称汗。
铁木真的强大引起了札木合的不快。于是，兄弟反目，发生了历史上著名的“十三翼之战”。后来，铁木真经过一系列对札木合的战争，不断取得胜利。
但在札木合的挑唆下，加之铁木真和义父王汗之间也产生了一些矛盾，王汗也在担心着一天天壮大的铁木真，故而，铁木真和王汗之间发生战争也在所难免。但最终，铁木真打败了王汗，夺取了王汗所属的土地和部族。
大会斡难河
铁木真击败王汗后，面前有两个敌人乃蛮部和塔塔儿人。这两个敌人一个是强大的草原部落，必须要消灭的对手；一个是和他有着杀父之仇，因此消灭他们也势在必行。铁木真开始策划吞并塔塔儿和乃蛮的战争。1202年，铁木真全歼了塔塔儿人，报了杀父之仇。1204年，铁木真消灭了乃蛮部太阳汗。铁木真最后逐一击溃强敌，统一了蒙古高原上的游牧部落，成为蒙古高原最强大的统治者。从此，铁木真的威名震动了蒙古高原，其他部落再也不敢同他争锋了。这样，铁木真就基本完成了统一全蒙古的大业。
1206年春，各部落首领在斡难河源头召开忽里勒台（大聚会的意思），铁木真被一致推举为全蒙古的大汗，并且上尊号为成吉思汗。这一年，铁木真四十四岁。巫师进言：“如今地上称为古尔罕的各国君主都被你征服，其领土都归你治下，因此你也应该有普天下之汗的尊号。上天旨意，你的称号应为成吉思汗。”至于“成吉思”的意思则有不同解释，有说为“天赐”之意，有说为“坚强有力”之意。但近人多采用伯希和的说法，认为它源于突厥语的“海”，是大海的意思。
延伸阅读
成吉思汗统一全蒙古以后，在军事、行政、法律、文化等各方面，都开创了一套新的制度。他把全体蒙古牧民编为十户、百户、千户和万户，任命大大小小的奴隶主为十户长、百户长、千户长和万户长，凡是十五岁以上、七十岁以下的男子，都编为士兵，平时生产，战时打仗。他任命失吉忽秃忽为“札鲁忽赤”（断事官），把民事和刑事案例编成“札撒黑”（习惯法）；他还委派兀孙老人掌管宗教事务；命令畏兀儿（就是现在的维吾尔族）人塔塔统阿用畏兀儿文字书写蒙古语，让贵族子弟学习使用，使蒙古人第一次有了文字。
