1209年春，成吉思汗的蒙古汗国已经建立四年，并派兵追击蔑里吉和乃蛮余部，射死了蔑里吉部的首领脱黑脱阿，赶走了太阳汗的儿子屈出律，同时已两征西夏，西夏战败。成吉思汗凯旋的信息传遍四方，对畏兀儿震动很大。“畏兀儿君主亦都护听得人们说成吉思汗强大和慷慨仗义，便倾向成吉思汗方面。他采纳了相国的建议，决定借助蒙古的力量乘机摆脱西辽的统治。他命令士兵们包围了西辽少监的住宅，西辽少监跑到楼上避难。畏兀儿的相国仳俚伽追上楼去，砍掉了这位少监的脑袋，然后让士兵推倒那座房子，将西辽少监埋葬在瓦砾堆中。
畏兀儿亦都护杀死西辽少监，公开宣告了与西辽的决裂，马上派出使者，准备去朝见成吉思汗，表示要归顺蒙古。但畏兀儿的使者还未出发，成吉思汗招降的使者已经到了高昌城。“亦都护对他们的莅临十分高兴，对他们很尊敬，表示了各种好感。“并立即让自己的两个使臣同他们一起去觐见成吉思汗。”
畏兀儿的使臣带去了一份国书，国书云：“我从来往的人们处听得吾王、世界征服者、宇宙之王的强盛、伟大、威严和坚强，便起来造了哈剌契丹古儿汗的反。我愿派遣使者完整、详细地向您报告我所知道的有关古儿汗的情况及其他任何情况，忠心耿耿地为您效劳。在考虑这些事的当儿，我仿佛觉得天空中乌云驱散，晴日当空。在阳光照射下，江面上冰封尽消，一江净水。我整个身心欢腾起来。自今以后，我要将全部畏兀儿国土献上，做成吉思汗的奴隶和儿子！”
畏兀儿的使者刚刚上路，蔑里吉部的首领脱黑脱阿的几个儿子忽都、赤剌温等，就带着脱黑脱阿的人头来到畏兀儿边界。他们派使者来见亦都护，希望与畏兀儿通好。“由于亦都护知道他们是成吉思汗的敌人，他不向他们屈服，同他们作战，将他们赶跑了。”随后，他又派出第二批使者向成吉思汗告捷。
成吉思汗十分赞许亦都护的举动，对畏兀儿的两批使者优礼相待，再次派出使者对亦都护进行慰劳，并下诏敕道：“如果亦都护真诚为我们效忠，可让他亲自从他的财产和帑藏中拿出一些东西来进贡。”于是，亦都护打开金库的门，取出些认为适宜的财物，然后动身去朝见成吉思汗。
1211年春，巴而术亦都护到克鲁伦河行宫去朝见了成吉思汗，向至尊表示臣服。他进献了表示归顺的礼物，并向成吉思汗奏道：“我们听见大汗的威名，就像乌云散尽，看见太阳一样；就像冰雪消融，看见清水一样，让人欣喜和高兴。如果能得有幸获得皇帝的赏赐，允许我们作为你管辖的国家，若蒙成吉思汗垂青，顾念臣下老远听到消息后立即前来而予抬举的话，请赐我以红袍金带，让我做成吉思汗四子以外的第五子，我将更加顺从，更加为他竭诚效劳！”成吉思汗为亦都护的忠心所感动，答应收他做自己的第五子。
成吉思汗道：“你既然愿意归附于我，我愿意收你为第五个义子。我还有一个漂亮的女儿，我可以把她送给你，作为你的妻子。”
成吉思汗将妃子生的女儿阿勒敦，许配给亦都护，作为他的新娘。亦都护对这件婚事也不推辞，只是说要等待回国后，再差遣人前来迎娶，但是亦都护回去，却杳无音信。
原来是因为亦都护的大老婆，妒忌心强，喜欢争风吃醋，不准许他另外迎娶新娘，所以就把事情耽误过去了，直到窝阔台接替大汗职位的时候，那时亦都护的大老婆已经死去了，才让亦都护完成了迎娶新娘的事情。
成吉思汗总是把别人的妻子和女儿，强夺过来作自己的妃子。也总是喜欢把自己的女儿送给别人当妃子，其实婚姻也是政治的延续，和亲也是一种政治手段。
从此畏兀儿亦都护成为蒙古国的贵戚，畏兀儿与蒙古的关系日益密切，“宠异冠于诸国”。当时，在中国北方，畏兀儿文化水平最高。直到这时成吉思汗还没有大量吸收汉文化，而是主要吸收畏兀儿文化。他还从畏兀儿族得到了不少人才，这对于蒙古的社会进步、对加强蒙古的政治统治都起了很大作用。同时，畏兀儿又是中西交通要道，往东南可直通西夏，往西可直通西辽。成吉思汗不费一刀一枪就降服了畏兀儿，从而打开了蒙古与西方交往的通道，这对成吉思汗征服西夏、西辽产生了很大影响。
降伏哈剌鲁
成吉思汗兵不血刃便降伏了畏兀儿，但是畏兀儿的同族哈剌鲁却没有这么听话。于是公元1211年，成吉思汗派忽必来出征哈剌鲁。哈剌鲁，又译合儿鲁、罕禄鲁、匣剌鲁、哈剌奴儿、柯耳鲁，唐代称葛逻禄，本为西突厥的一部。西突厥被唐军打败后，葛逻禄人先是迁到北庭附近，后又进入伊犁河、楚河一带。公元840年，回鹘汗国被黠戛斯颠覆后，有一支回鹘人迁徙到葛逻禄族居住的地区，后来逐渐与葛逻禄人融合为一个民族，这就是哈剌鲁。
公元10世纪中叶，当五代末年、北宋初年之际，回纥撒吐克喀拉汗在中亚细亚建立喀拉汗国，又译哈剌汗国，开始崇拜伊斯兰教。哈剌汗国曾攻占阿姆河北岸的布哈拉城，并曾灭掉阿姆河北岸的波斯萨曼王朝。因此《史集》记载，哈剌鲁与畏兀儿具有同一的族源，当他们的一个祖先乌古思放弃佛教、改信伊斯兰教时，内部发生了战争。“对那些归附于他并成为他的协助者的人，乌古思赐以畏兀儿之名。”而当乌古思在一次战争中从战场返回老营时，“在途中到了一座大山下，当时下了一场雪；有几个家族由于下了这场雪，落后了”，乌古思便给这几个家族起名为哈剌鲁，意即有雪者、“雪人”，哈剌鲁诸部都出自这些人。
西辽统治时期，哈剌鲁成为西辽的附属国，其统治区域包括阿尔泰山以西、伊犁西北、巴尔喀什湖东南一带，主要包括三座城：海押立，今苏联巴尔喀什湖东、卡帕尔城附近；阿力麻里，又作“阿力马力”、“阿里马”，意为苹果城，其故址在今新疆霍城西北克根河西岸、阿尔泰古城一带；不剌城，又译普剌城，今新疆博乐县。
成吉思汗兴起前，哈剌鲁有两个国王，分别驻在海押立和阿力麻里城。驻在海押立城的哈剌鲁首领称为阿儿思兰汗，这是一个世袭的称号。西辽的菊儿汗（古儿汗）派了一名沙黑纳（少监）协助阿儿思兰汗管理该地的政事。西辽末年，周围的附属国先后起来反抗西辽的统治，忽炭的算端（伊斯兰教国家君主的称谓，又译苏丹）也起兵造反。菊儿汗决定率军讨伐忽炭的算端，同时命令阿儿思兰汗参战。他这样做，动机是要把阿儿思兰汗置于死地；由此，若阿儿思兰汗也和其他君主一样谋反，他就可以干脆把他除掉；另外，若他表示服从，但对穆斯林（伊斯兰教徒）温情脉脉，讨伐忽炭不力，那也可以以此为借口，同样要了他的命。
阿儿思兰汗并没有识破菊儿汗这个阴谋，遵命率领部队去与菊儿汗会合。菊儿汗的一名侍从官，名叫沙木儿-塔阳古，他平时与阿儿思兰汗很有交情，偷偷地把菊儿汗这个阴谋告诉了阿儿思兰汗。阿儿思兰汗不知所措，沙木儿-塔阳古给他出了一个主意，道：“要是菊儿汗对你下毒手，你的家室子女也将绝灭。替你的子女的前途着想，你最好的办法莫如服毒自尽，以此摆脱这不幸人生的苦难和那残暴的君主。到时我将替你说话，让你的儿子继承你的位子。”阿儿思兰汗别无逃生之路或避难之地，只好含泪喝下了一杯毒酒，一命归天了。
沙木儿遵守诺言，为阿尔思兰汗的儿子争得了汗位，这就是马木笃汗，习惯上仍称为阿尔思兰汗。菊儿汗派了另一名监护官去监护马木笃汗。这位西辽的监护官也像菊儿汗那样阴险残忍，他根本不把马木笃汗当可汗对待，任意侮辱，无所不用其极；对哈剌鲁的臣民百姓更加专横暴虐。马木笃汗君臣早就对这位监护官恨之入骨了。当成吉思汗派忽必来率军开入哈剌鲁境内时，马木笃汗也学习畏兀儿的榜样，杀死了那位可恶的西辽少监，率领臣民开城投降了蒙古。马木笃汗随同忽必来去朝见成吉思汗，并将表示归顺的礼物进献到怯绿连（河）地方，向成吉思汗表示臣服，归顺了他。成吉思汗为了表彰马木笃汗不战而降，决定“赐以女”，允许他“和一个蒙古公主成亲”。后来，哈剌鲁一带成为察合台汗国的一部分，后又成为窝阔台之孙海都的领地。阿儿思兰汗的几代子孙都与蒙古的公主结婚，在政治上享有很高的地位。
哈剌鲁的另一个首领名叫斡匝儿（不丰），他原来是拦路抢劫的强盗，是一个勇猛绝伦的汉子。他经常偷盗别人的马匹，还干其他犯罪勾当。由于受到当地一些歹徒的拥护，他变得十分强大。他们经常进攻周围的村落，谁起来反抗，他们就用武力征服。他们的势力日益发展，最后竟攻占了阿力麻里，并攻占了不剌城，居然建立了一个割据政权，斡匝儿被拥立为脱黑鲁儿汗。
1211年，乃蛮部太阳汗之子屈出律夺取了西辽政权。乃蛮原来信奉景教，屈出律娶的西辽公主信奉佛教。于是屈出律强迫当地和附属国的人民改信佛教或景教。斡匝儿是一个伊斯兰教徒，被迫起来反对屈出律的统治。屈出律屡次派兵攻打他，但往往被他打败。为了对付屈出律，他派出使者朝见成吉思汗，上报有关屈出律的情况，自称是成吉思汗的臣仆。成吉思汗派人对他进行慰劳，后来又把术赤的女儿嫁给了斡匝儿的儿子，与他结为姻亲。当他作为藩属的基础巩固后，遵照成吉思汗的诏旨，他亲身赴朝，在那里得到殷勤的接待。临行前，成吉思汗嘱咐他戒猎，免得突然成为他人的猎物。为了不让斡匝儿再外出打猎，成吉思汗特地赠送他一千只羊，用以代替猎物。但斡匝儿出身强盗，喜欢游乐，一直热衷于狩猎活动。他返回阿力麻里后，无论如何也克制不住打猎的欲望。有一次出外打猎，由于他毫无戒备，终于在猎场上被屈出律的士兵捕获了。他们用铁链子拴着他，把他带到阿力麻里城前，企图让他叫开城门，占领这座城市。阿力麻里人关闭城门，起来抵抗屈出律的军队。这时，忽然传来蒙古军队前来支援的消息，屈出律的军队如惊弓之鸟，赶紧撤军，在半路上杀死了斡匝儿。斡匝儿死后，他的儿子昔格纳黑的斤继承了他的位子，受到成吉思汗的恩宠，直到他的几代子孙还奉命治理阿力麻里。
