铁木真带着黑貂皮斗篷作为礼物来到土兀刺［土拉］河畔朝见克烈部的强大首领脱斡邻勒，并向他表示效忠（约1175年？）。脱斡邻勒念其父曾有援助之恩，欢迎这位年轻人，并把他纳入自己的属臣之列。从此，两人结为盟友，尽管铁木真明显地是处于属臣地位。这一点从“汗，我的父亲”这一称号上明显地反映出来。在下文（下一节）引用的铁木真给克烈首领的著名信中，就是用这种称号。
此后不久，铁木真遭到由脱脱别乞首领率领的一伙蔑儿乞人的袭击。只是在铁木真的妻子孛儿帖作为俘虏落入敌人之手后，铁木真才得以逃脱（入肯特山）。铁木真得到克烈部统治者脱斡邻勒的帮助，同时也得到另一位蒙古首领、与他同龄的札只刺惕部人礼木合的帮助。三人在色楞格河支流不兀刺川［布拉河］共同击败了鹿儿乞人，夺回孛儿帖。孛儿帖恢复了她在家族中的至尊地位。孛儿帖不久生下的孩子——法定的长子术赤到底是铁木真之子呢，还是篾儿乞绑架者赤勒格儿力士之子，铁木真对此从未探究过。然而，关于对术赤出生的未声张的疑点很可能是妨碍这位长支之首——或者他的后代们——在成吉思汗的王位继承中扮演主要角色的因素。
同时，尽管铁木真和札木合是安答，或称结义兄弟，但不久发生争吵，两人的目标都是要在对自己有利的条件下恢复原蒙古王室，并被承认为汗。
《秘史》叙述了他们一起在斡难河的合儿部纳黑·朱布儿地区漫游了一年半之后分手的情况。这是最后一位蒙古汗忽图刺庆祝他当选的地方，它很可能激起了两位年轻首领的野心。铁木真在山中扎营，札木合在河边扎营。札木合曾说过：“山坡上是养马者的帐幕，河边是牧羊者的牧场。”巴托尔德和符拉基米尔佐夫由此得出结论：铁木真得到养马者、“草原贵族们”的支持；札木合得到贫苦牧民、即平民，或称哈刺抽的支持。《秘史》继续记道，札木合“喜新事物而轻传统”。符拉基米尔佐夫由此推断札木合是某种民主派的代表，而成吉思汗代表贵族，这种解释显得非常轻率。无论俄国学者们争论的核心是什么，事实是，铁木真和札木合分手后，“札刺儿部、乞颜部和八邻部”跟随着铁木真，在他这边还有蒙古贵族联盟中地位最高的代表：他的叔叔答力台·斡赤金和著名的合不勒汗的长支后裔，其中有合不勒汗的曾孙（斡勒巴儿合黑之孙）、主儿乞部首领撒察别乞和忽图刺汗之子阿勒坦斡赤斤。换言之，他赢得了最末两代蒙古王后裔们的支持。符拉基米尔佐夫解释了《秘史》中的一段，他认为在争夺新王室的两者之中，原王室的代表们倾向铁木真，因为他们判断铁木真在世界观上要更加守旧些和要驯服些，而札木合的活跃性格和革新倾向使他们疑虑不安。原王室合法继承人阿勒坦无疑是出于投机的原因谢绝了汗的称号，有些犹豫地把我们不妨称之为正统王权拥护派的票投给了铁木真，结果，铁木真当选。阿勒坦和撒察别乞是最早宣布铁木真为汗（即蒙古人的王）的人，这次选举比1206年铁木真被选为中亚突厥－蒙古各族人的最高汗（或称皇帝）的选举早10年。作为王，铁木真采用chinggiskhan一名，一般史书写成Jenghiz
khan。学者中对该名的准确含义仍有争执。
除了政治上的考虑外，为了掩护，某些宗教因素有利于这次选举。早些时候八邻首领火儿赤宣布：“天国（腾格里）注定铁木真将成为我们的汗。这是圣灵向我揭示的，我又向你们揭示。”同样来自天国之命的又一种说法是人们可以称之为“木华黎预言”。有一天，当铁木真在合儿郭纳黑·朱布儿扎营时，札刺儿部木华黎提醒他，在同一地点，同一棵树下，取得汗号的最后一位蒙古首领忽图刺曾经在此歌舞宴会庆祝他的登位。“从那时起，蒙古人经历了苦难的日子，他们中不再有汗。但长生天没有忘记它的人民，即忽图刺家族。蒙古人中将产生英雄，一位令人恐惧的汗，为他们的苦难报仇……”。除了这些引语所表达的宗教外壳外，成吉思汗的当选使人们产生选出了战争和狩猎中的领袖的印象。他的选民——阿勒坦、火察儿和撒察别乞——立下了誓言，《秘史》复述了这些庄严的誓言：“立你做皇帝。你若做皇帝呵，多敌行俺做前哨，但掳来的美女妇人并好马，都将来与你；野兽行打围呵，俺首先出去，围将野兽来与你。”
有一个人可能会（也应该）对这个新的政权感到不安，他就是克烈部首领脱斡邻勒。他看到昨天的属臣正在走向与他平等的地位。但是，脱斡邻勒是个缺乏想象力的、优柔寡断和平庸的首领，他没有认识到这件事的含义，加上新当选的成吉思汗更谨慎地声称自己比以往任何时候都更加自觉地忠实于他。况且，当时的形势无疑也令脱斡邻勒放心，成吉思汗还远未能把蒙古人统一起来，在他的面前，反对他的札木合也有自己的党羽。此外，克烈王与成吉思汗有着同样的外敌——塔塔儿人。
我们已经看到成吉思汗忠实的支持者之一，札刺儿部的木华黎，他劝成吉思汗称汗，据《秘史》记，他是唤起成吉思汗回忆蒙古人与塔塔儿人之间的世仇而达到目的的。正是塔塔儿人把原蒙古王室的两位成员引渡给金朝，使他们遭受凌辱；正是塔塔儿人于1161年与金联合，灭了蒙古人的第一个王权；也正是他们，约于1167年在草原上举行的一次友好宴会上背信弃义地在食物中放毒毒死了成吉思汗之父也速该。“呵铁木真，你应该为汗，向我们的敌人塔塔儿人报仇，你应该恢复蒙古人的光荣。”
机会来了。塔塔儿人似乎只是在金朝的援助下才战胜了蒙古人。但是，一旦胜利使他们成了东戈壁的主人，他们就常常骚扰金国边境。北京朝廷改变了联盟的对象，决定援助和挑动克烈王脱斡邻勒对付塔塔儿人。作为克烈王的忠实属臣，成吉思汗陪同出征（约1198年），有幸能够向他自己的仇敌报仇。贝尔湖畔的塔塔儿人在受到来自东南方向的金军和来自西北方向的克烈人和成吉思汗的夹击下遭到了惨败。据《秘史》记，克烈王和成吉思汗沿斡里札河进军，杀塔塔儿王蔑古真·薛兀勒图。北京朝廷封赏脱斡邻勒为汉号“王”（王或王子），因此，脱斡邻勒在历史上被称为王罕。成吉思汗也接受了中国的封号，但是，官位低多了，它说明当时北京朝廷只把他看成是克烈人手下的一位微不足道的属臣而已。
符拉基米尔佐夫认为，正是这次战争以后，成吉思汗惩罚了大批的蒙古王公、原王室后裔，因为他们拒绝随他和王罕出征去打塔塔儿人。他处死了著名的合不勒的曾孙、主儿乞（或主儿金）部首领撒察别乞，以及另外两位王公泰出和不里孛阔。在写给王罕的著名的声诉信中，他声称，为了给克烈人报仇他牺牲了“他深深热爱的这些兄弟们”。事实上，他必定很高兴找到了非常恰当的借口，使他摆脱了所谓“蒙古正统性”的代表人物。
如果我们遵循成吉思汗正史上的说法，那么，成吉思汗与王罕之间的联盟似乎主要是对王罕有利。无论如何，如果说王罕最初的保护使成吉思汗能够免遭他的敌人的侵害的话，那么，这位蒙古英雄很快对他的宗主奉献出同样的义务。在难以确定的一段时期中，王罕发现自己被其兄弟额尔客合刺推翻，后者得到了乃蛮王亦难赤必勒格的支持。王罕向西南方逃亡，直到楚河，逃到喀喇契丹人中，他徒劳地希望能得到喀喇契丹王的帮助。在与该王（或称古儿汗）发生争吵之后，他在戈壁滩上过着悲惨的流浪生活，对复位丧失了信心，他到成吉思汗那里避难。成吉思汗救济了他的饥饿的小队人马，帮助他重新夺回了克烈部地盘。正是因为这些，以后成吉思汗用朴实婉转的话语提醒克烈王：“君