1209年春，成吉思汗的蒙古汗國已經建立四年，並派兵追擊蔑裏吉和乃蠻餘部，射死了蔑裏吉部的首領脫黑脫阿，趕走了太陽汗的兒子屈出律，同時已兩征西夏，西夏戰敗。成吉思汗凱旋的信息傳遍四方，對畏兀兒震動很大。“畏兀兒君主亦都護聽得人們說成吉思汗強大和慷慨仗義，便傾向成吉思汗方麵。他采納了相國的建議，決定借助蒙古的力量乘機擺脫西遼的統治。他命令士兵們包圍了西遼少監的住宅，西遼少監跑到樓上避難。畏兀兒的相國仳俚伽追上樓去，砍掉了這位少監的腦袋，然後讓士兵推倒那座房子，將西遼少監埋葬在瓦礫堆中。
畏兀兒亦都護殺死西遼少監，公開宣告了與西遼的決裂，馬上派出使者，準備去朝見成吉思汗，表示要歸順蒙古。但畏兀兒的使者還未出發，成吉思汗招降的使者已經到了高昌城。“亦都護對他們的蒞臨十分高興，對他們很尊敬，表示了各種好感。“並立即讓自己的兩個使臣同他們一起去覲見成吉思汗。”
畏兀兒的使臣帶去了一份國書，國書雲：“我從來往的人們處聽得吾王、世界征服者、宇宙之王的強盛、偉大、威嚴和堅強，便起來造了哈剌契丹古兒汗的反。我願派遣使者完整、詳細地向您報告我所知道的有關古兒汗的情況及其他任何情況，忠心耿耿地為您效勞。在考慮這些事的當兒，我仿佛覺得天空中烏雲驅散，晴日當空。在陽光照射下，江麵上冰封盡消，一江淨水。我整個身心歡騰起來。自今以後，我要將全部畏兀兒國土獻上，做成吉思汗的奴隸和兒子！”
畏兀兒的使者剛剛上路，蔑裏吉部的首領脫黑脫阿的幾個兒子忽都、赤剌溫等，就帶著脫黑脫阿的人頭來到畏兀兒邊界。他們派使者來見亦都護，希望與畏兀兒通好。“由於亦都護知道他們是成吉思汗的敵人，他不向他們屈服，同他們作戰，將他們趕跑了。”隨後，他又派出第二批使者向成吉思汗告捷。
成吉思汗十分讚許亦都護的舉動，對畏兀兒的兩批使者優禮相待，再次派出使者對亦都護進行慰勞，並下詔敕道：“如果亦都護真誠為我們效忠，可讓他親自從他的財產和帑藏中拿出一些東西來進貢。”於是，亦都護打開金庫的門，取出些認為適宜的財物，然後動身去朝見成吉思汗。
1211年春，巴而術亦都護到克魯倫河行宮去朝見了成吉思汗，向至尊表示臣服。他進獻了表示歸順的禮物，並向成吉思汗奏道：“我們聽見大汗的威名，就像烏雲散盡，看見太陽一樣；就像冰雪消融，看見清水一樣，讓人欣喜和高興。如果能得有幸獲得皇帝的賞賜，允許我們作為你管轄的國家，若蒙成吉思汗垂青，顧念臣下老遠聽到消息後立即前來而予抬舉的話，請賜我以紅袍金帶，讓我做成吉思汗四子以外的第五子，我將更加順從，更加為他竭誠效勞！”成吉思汗為亦都護的忠心所感動，答應收他做自己的第五子。
成吉思汗道：“你既然願意歸附於我，我願意收你為第五個義子。我還有一個漂亮的女兒，我可以把她送給你，作為你的妻子。”
成吉思汗將妃子生的女兒阿勒敦，許配給亦都護，作為他的新娘。亦都護對這件婚事也不推辭，隻是說要等待回國後，再差遣人前來迎娶，但是亦都護回去，卻杳無音信。
原來是因為亦都護的大老婆，妒忌心強，喜歡爭風吃醋，不準許他另外迎娶新娘，所以就把事情耽誤過去了，直到窩闊台接替大汗職位的時候，那時亦都護的大老婆已經死去了，才讓亦都護完成了迎娶新娘的事情。
成吉思汗總是把別人的妻子和女兒，強奪過來作自己的妃子。也總是喜歡把自己的女兒送給別人當妃子，其實婚姻也是政治的延續，和親也是一種政治手段。
從此畏兀兒亦都護成為蒙古國的貴戚，畏兀兒與蒙古的關係日益密切，“寵異冠於諸國”。當時，在中國北方，畏兀兒文化水平最高。直到這時成吉思汗還沒有大量吸收漢文化，而是主要吸收畏兀兒文化。他還從畏兀兒族得到了不少人才，這對於蒙古的社會進步、對加強蒙古的政治統治都起了很大作用。同時，畏兀兒又是中西交通要道，往東南可直通西夏，往西可直通西遼。成吉思汗不費一刀一槍就降服了畏兀兒，從而打開了蒙古與西方交往的通道，這對成吉思汗征服西夏、西遼產生了很大影響。
降伏哈剌魯
成吉思汗兵不血刃便降伏了畏兀兒，但是畏兀兒的同族哈剌魯卻沒有這麼聽話。於是公元1211年，成吉思汗派忽必來出征哈剌魯。哈剌魯，又譯合兒魯、罕祿魯、匣剌魯、哈剌奴兒、柯耳魯，唐代稱葛邏祿，本為西突厥的一部。西突厥被唐軍打敗後，葛邏祿人先是遷到北庭附近，後又進入伊犁河、楚河一帶。公元840年，回鶻汗國被黠戛斯顛覆後，有一支回鶻人遷徙到葛邏祿族居住的地區，後來逐漸與葛邏祿人融合為一個民族，這就是哈剌魯。
公元10世紀中葉，當五代末年、北宋初年之際，回紇撒吐克喀拉汗在中亞細亞建立喀拉汗國，又譯哈剌汗國，開始崇拜伊斯蘭教。哈剌汗國曾攻占阿姆河北岸的布哈拉城，並曾滅掉阿姆河北岸的波斯薩曼王朝。因此《史集》記載，哈剌魯與畏兀兒具有同一的族源，當他們的一個祖先烏古思放棄佛教、改信伊斯蘭教時，內部發生了戰爭。“對那些歸附於他並成為他的協助者的人，烏古思賜以畏兀兒之名。”而當烏古思在一次戰爭中從戰場返回老營時，“在途中到了一座大山下，當時下了一場雪；有幾個家族由於下了這場雪，落後了”，烏古思便給這幾個家族起名為哈剌魯，意即有雪者、“雪人”，哈剌魯諸部都出自這些人。