13世纪初，成吉思汗统一蒙古各部，继而率军西征。1209年，高昌亦都护(王)巴而术阿而忒的斤(即前述之高昌回鹘首领)毅然杀死西辽派往该地的“镇守官”，率先归附蒙古。成吉思汗以其为第五子，并将女儿许配给他为妻。接着，蒙古大军灭西辽，越太和岭(今高加索山)，攻人钦察，进掠斡罗思(今俄罗斯)南部边境地区。

成吉思汗西征，历史七年，蒙古铁骑踏遍中亚以及里海周围的欧洲地区。1225年，成吉思汗将其征服的土地，分授给三个儿子：长子术赤统辖今里海以北及原花刺子模王国的领土；次子察合台统辖东至伊犁河流域，包括焉耆以西地区，西至阿姆河流域的土地；三子窝阔台统辖准噶尔盆地北部、阿尔泰地区和蒙古的西部。另外，由于最先降服蒙古，高昌亦都护被允准保留自己的领地。成吉思汗三个儿子的封地，后来逐渐演变成了钦察、窝阔台、祭合台三个汗国。三个汗国的汗可以在自己的封地内开府设官，但必须接受蒙古大汗任命的总管和各地的达鲁花赤(断事官)对封地实施行政管理。就连封地内的赋税，三个汗国的汗也不能征收，而只能分得其中的一部分。1251年，蒙哥汗即位后，在别失八里(今新疆吉木萨尔县)和阿姆河等处设立行尚书省，管辖新疆和中亚地区。

1271年，忽必烈建立元朝后，加强了对新疆地区的管理，先后在阿力麻里(今新疆霍城县)、哈刺火者(高昌)、和阗等地设立元帅府以管理军事，设立按察司、宣慰司、提督司、交钞库等机构以管理民刑、财政。除此以外，元朝还在新疆实行屯田，设置驿站，发行货币，建立织造局和冶炼场等，不仅促进了社会经济的发展，也加强了新疆与内地的联系。

元末，由于元朝内讧迭起，无力西顾，成吉思汗的次子察合台的后裔实际上控制着新疆和中亚地区。1347年，察合台汗国分裂为东、西两部分：西部为广大的中亚绿洲地区，后来演变为帖木儿帝国；东部为天山南北广大地区，史称“东察合台汗国”。东察合台汗国王驻阿力麻里，蒙古贵族充任各地长官，管理军政事宜。

关于哈密卫

1368年，明朝建立，西域各地纷纷遣使朝贡。为开辟同西方各地的陆路贸易通道，明朝亦曾派军西行。1391年，因哈密蒙古宗王时常阻止使臣商旅往还明朝，企图垄断贡利，明太祖令左军都督、佥事刘真、宋晟率军征伐之。哈密蒙古宗王兀纳失里率残众逃匿。次年，“遣使贡马骡请罪”。1404年，明朝封哈密王安克帖木儿为忠顺王， “使守其地，绥抚其民”。1406年，明朝设哈密卫。哈密卫的建立，使该地区置于明朝直接统治之下。“由是，诸番唇齿之势成，华夷内外之合力，边境守谧余八十年” 取一种较为松散、灵活的羁縻方式，与他们保持着密切的政治经济联系。东察合台汗国诸首领亦视明朝为其共主，遣使朝贡，乞请册封。凡来朝觐贡献者，明朝俱予以赐赉；乞请册官者，细经查询，也予以委命。先后受到明朝册封的有别失八里王、亦力把里王、吐鲁番王和瓦剌王等。然而，新疆的大部分地区实际上为东察合台汗国以及后来的叶尔羌汗国所控制。