鐵木真已經有了一套文字，也有了一支軍隊，他可以建國了。為了使這個新時代一開始就與眾不同，他為自己選擇了一個簡短而威嚴的頭銜。他對傳統的頭銜古兒汗根本不感興趣，因為戴著這個頭銜的很多惡人下場悲慘，用一位基督教牧師的話說：“其榮耀永遠與汙點相伴。”[183]因此，他自己選擇了成吉思汗這個新的蒙古頭銜，這個頭銜代表堅定、強大、剛毅和忠誠，同他自己名字鐵木真所代表的品質類似。在蒙古語中，“成”(Chin)的意思是“決心”或者“堅強的意誌”，因此，他成為了“強大的君主”或“強大的汗”。漢文史料中最早提及他的稱號是在1221年宋朝特使趙珙提交給朝廷的報告中，說他的頭銜的意思是“天賜”。[184]
對他的蒙古追隨者來說，鐵木真成了成吉思汗，但對他的突厥追隨者來說，他是騰吉斯，意思是“海洋”。自從匈奴時代以來，這個名字就有著豐富的含義，阿提拉和他的兒子都擁有這個稱號。幾個世紀以來，草原統治者都把這樣表示水的稱號加給他們的領袖，但形式各有不同，如回鶻的Bilge Kol，意思是“智海”，或叫達賴汗，意思是“四海之內的統治者”。[185]
1206年夏天，奠定新帝國根基的時機已經成熟，成吉思汗決定回到不兒罕聖山腳下，斡難河的源頭。差不多四十年前，他的母親曾以此地為避難所。她曾在河邊來回奔走，手裏拿著一根黑木棍，挖掘根莖養活她的孩子們。[186]現在，他選擇此地作為他的新國家的根基，一則是對他的精神家園表達敬意，二則是對他母親的深深崇敬。母親曾目睹他畢生的鬥爭，還將活著看到他的勝利。盡管得到了這些榮譽，她還是很不滿意，因為成吉思汗隻給她的宮廷分配了五千個臣民。
沒有外國人在場見證蒙古帝國的誕生，但後來的曆史學家根據所掌握的資料，有時加上自己的想象，描述了蒙古帝國創立的過程。在《弓箭手民族的曆史》(History of the Nation of Archers)一書中，亞美尼亞史家格雷戈裏(Gregory of Akner)寫道，蒙古人向神祈求，救贖他們脫離可憐、悲慘的生活；神聽見了他們的禱告，並派來了天使，就是鐵木真在異象中看見的那隻有著金色羽毛的老鷹；老鷹天使站在開闊地帶，距鐵木真大約一箭遠的地方，宣布他的新稱號，接著便為這個新民族頒布法律。[187]