於是，他們飲酒盟誓，立鐵木真當可汗。這一年，鐵木真三十三歲了。
鐵木真當上可汗以後，為了加強自己的權力和防止鄰部的襲擊，又重新整頓了軍隊，成立了專門保衛自己的侍衛隊，還建立了訓練戰馬、管理戰車的專門機構，勢力一下子擴大了許多。
鐵木真的壯大，引起劄木合的警惕。劄木合本來就對鐵木真拉走他的部下不滿，又加上他的弟弟因搶奪鐵木真部下的馬群被殺死，劄木合更是氣得暴跳如雷，決心進行報複。他立即集合所屬的十三部三萬人馬，殺氣騰騰地來與鐵木真決戰。鐵木真也將他的三萬士兵分成十三翼迎戰劄木合。
雙方在克魯倫河畔相遇了。千軍萬馬全絞殺在一起，直殺得天昏地暗，血流遍地。這就是蒙古曆史上著名的“十三翼之戰”。
劄木合終歸是實力雄厚的大貴族，他手下的兵馬久經訓練，在戰場上猛衝猛打，漸漸占了上風。鐵木真看到自己的士兵抵擋不住，隻好指揮人馬退到鄂倫河邊的一個峽穀中去。劄木合乘勝追擊，俘虜了許多人馬才撤走。
劄木合退回住地後，發現有些俘虜就是原來依附自己的人。他痛恨這些人背叛了他，就命令部下支起七十口大鍋，把背叛他的貴族活活地煮死，還把為首的兩個部族首領的頭砍下來拴在馬尾巴上，拖著在人群中跑來跑去。
劄木合想用殘酷的手段來威脅手下的部落。誰知恰恰相反，劄木合手下一些小部落的首領見他這樣殘酷無情，都寒了心，一個跟著一個地帶著百姓去投靠鐵木真去了。因此，鐵木真雖然在“十三翼之戰”中戰敗了，壞事卻變成了好事，劄木合部下的許多奴隸主、屬民和奴隸反而成了鐵木真新的支持者。
鐵木真看到這麼多的人來投靠他，真是喜出望外。他在樹林中熱情款待新來的部族首領，好言好語地安慰他們。鐵木真的勢力又壯大起來。
鐵木真在蒙古高原上崛起以後，和其他蒙古部落的矛盾越來越大。於是，有十一個部落的首領聯合在一起，推選劄木合為“天下之汗”，出兵攻打鐵木真。鐵木真率軍迎戰，結果劄木合的軍隊大敗。鐵木真又乘勝進軍，征服了許多部落，統一了大半個蒙古。
這樣，在統一全蒙古的道路上，鐵木真剩下的最後的對手，就是蒙古西部的乃蠻部了。
1204年夏天，鐵木真率領大軍出征乃蠻。乃蠻部首領塔陽汗則率領聲勢浩大的隊伍抵擋。雙方擺好陣勢後，恰巧鐵木真軍營中的一匹瘦馬受驚跑入乃蠻營中。塔陽汗一看這匹馬瘦成這個樣子，以為鐵木真的軍隊一定不堪一擊。他親自出馬向鐵木真挑戰，鐵木真的騎兵經過長期訓練，真是今非昔比，不但個個騎術高超，刀法純熟；而且臨陣不亂，進退有序。到了下午，乃蠻的軍隊漸漸招架不住了，塔陽汗也在混戰中被殺死。天黑以後，乃蠻軍隊再也無心抵抗，一下子潰散了。他們在黑夜中相互擁擠，掉下懸崖摔死的就不計其數，隻有少數軍隊在塔陽汗的兒子率領下逃脫。
這場大戰之後，乃蠻部的百姓都成了鐵木真的俘虜，鐵木真的名字震動了整個蒙古高原。鐵木真統一全蒙古的大業完成了。
1206年，鐵木真在斡難河的源頭樹起九麵裝飾著流蘇（穗狀裝飾物）的白色大旗，召集全蒙古的貴族舉行大會。會上依照蒙古族的習俗，擺上整隻的熟羊和整桶的馬奶酒，姑娘們載歌載舞，小夥子們舉行摔跤比賽，貴族們痛痛快快地喝酒玩樂，草原上像過節一樣熱鬧。
忽然，從大帳中走出一個珊蠻（就是僧侶）。他臉色嚴肅地高聲說：“天說，讓鐵木真當成吉思汗（意思是最強大的王），治理地上的百姓！”人們立刻安靜下來，定睛一看，原來是鐵木真身邊的珊蠻闊闊出。那時候，蒙古部族的人信奉珊蠻教，遇到大事，都要請珊蠻占卜吉凶，代神說話。闊闊出是鐵木真身邊最大權勢的珊蠻。他常常說自己騎著一匹灰色的馬從蒙古包的天窗升天，和天說話，人們對他深信不疑。大夥立即恭敬地推舉鐵木真為全蒙古的大汗，號就是“成吉思汗”。
鐵木真稱汗的那天，草原上搭起了金頂大帳，他身穿黃袍，踏著紅地毯，走進大帳，周圍的人都虔誠地跪下磕頭。成吉思汗成為全蒙古的最高首領，標誌著過去分散的部落合成了一個共同體。從此，他們開始使用“蒙古”這個名稱。勤勞勇敢的蒙古族開始了新的曆史進程。
成吉思汗把全蒙古的土地分封給他的親屬和大大小小的奴隸主。牧民被編為十戶、百戶、千戶和萬戶，由各部首領管理。凡十五歲以上、七十歲以下的男子，統統被編為士兵，平時放牧，戰時出征。為了加強自己的地位，成吉思汗選拔貴族的子弟組成一支精銳部隊，稱“怯薛”，由自己親自控製。除此以外，成吉思汗還建立了司法機構，製定了初步的成文法，命人創立了蒙古文字。在建立政權的過程中，成吉思汗顯示了很強的組織才能。
闊闊出因為擁立鐵木真當成吉思汗有功，逐漸變得蠻橫驕縱起來。有一天，闊闊出和他的兄弟把成吉思汗的弟弟合撒兒打了一頓。事後，他還到成吉思汗麵前挑拔說：
“天說，一次讓鐵木真治理百姓，一次讓合撒兒治理百姓。您可要提防合撒兒呀！”
成吉思汗一聽就急了，馬上親自去審問合撒兒。成吉思汗的母親聽到這件事，慌忙也跟著去了。老人家走進合撒兒的帳蓬，見成吉思汗正在審訊合撒兒。她就盤腿坐在地毯上，責問成吉思汗：
“這是奶你們的，隻吃了這隻；合撒兒兩隻都吃過。你們都是我的乳汁養大的。合撒兒有力氣，箭法好，替你出生入死地打仗。現在討平了敵人，你就容不得他了。聽任外人的挑撥，想治自己的兄弟！”