兩晉南北朝時期
三國魏、西晉時新疆仍然為中國領土。4世紀初,西晉因來自北方的遊牧民族入侵而覆滅,歷史進入五胡十六國時期。此間在中國西北部建立了一個又一個的不同民族的國家,包括前涼、前秦、北涼、後涼和西涼。如東晉太元八年(383年)前秦將軍呂光受命率7萬余眾討平西域。苻堅淝水之戰兵敗後前秦瓦解,呂光據有姑臧(今甘肅武威)于太元十一年(386年)稱大將軍、涼州牧。太元十四年(389年)呂光稱三河王,後改稱天王,史稱後涼。 統治范圍包括甘肅西部和寧夏、青海、新疆一部分。另外十六國時期維吾爾人祖先丁零人翟遼在今天河南黃河南岸建立的政權國號魏,史稱翟魏,392年為後燕慕容垂所滅。這些政權都試圖保持對新疆諸藩的控制。最終鮮卑的北魏重新統一中國北方,控制了今天新疆東南的一部分。疏勒、于闐、龜茲和且末等政權控制了西部,而中央吐魯番附近則被北涼的延續者高昌所統治。 南北朝末期,西域出現了社會大動蕩和民族大融合的局面。
5世紀末,吐谷渾和柔然開始分別侵入新疆南部和北部,中原政權(北朝)逐漸喪失對此地的控制。從6世紀開始,突厥在阿爾泰山地區崛起,數年間擊敗柔然,建立了西至鹹海、東抵大興安嶺、橫亙中亞的突厥汗國。583年突厥分裂為東西二部,新疆屬西突厥。
隋唐時期
隋唐時期是我國封建社會空前繁榮、昌盛的時期。西元608年,隋朝在打敗了連年入侵的吐谷渾之後,控制了今日的新疆東南部。開始之後中原王朝經營西域。
唐太宗貞觀十四年(640年),唐軍佔領高昌,于該地置西州,又于可汗浮圖城(今吉木薩爾)設庭州;同年在高昌設安西都護府,後遷至庫車,改置為安西大都護府。統安西四鎮:龜茲、疏勒、于闐、碎葉(今吉爾吉斯斯坦的托克馬克市),轄境相當今新疆及哈薩克東部、吉爾吉斯北部楚河流域。自顯慶元年(656年)至麟德元年(664年),這期間,是武則天為皇後輔佐高宗到垂簾聽政階段。在之後的二十年間,唐軍發動了對西突厥的一係列遠徵,唐高宗發大軍分南北兩道進攻西突厥,一舉滅掉了西突厥,在657年西突厥徹底投降,西突厥領土全部為唐所有。顯慶、龍朔年間(661-663年),唐軍平定西突厥,轄區擴大至今阿爾泰山西至鹹海及蔥嶺的東西各部直至阿姆河兩岸城的諸城邦國包括今新疆大部分。670年安西四鎮被吐蕃攻佔,693年武周再次佔領。唐朝鹹亨元年(670年),安西都護府治所移至碎葉城。702年在庭州設置北庭都護府,後又升為北庭大都護府,管理天山北麓及新疆東部地區的軍政事務,而安西大都護府管理天山南部和蔥嶺以西的廣大地區。唐玄宗開元年間,曾在兩大都護府之上設磧西節度使,是當時全國八大節度使之一。非漢民聚居區,則設置羈縻府州。同時,還在龜茲、于闐、疏勒、碎葉(一度是焉耆)設軍事建制,史稱安西四鎮。唐朝前中期,在西域的領土一直延伸到現在中亞的鹹海。設立安西都護府管轄,都護府下面設都督府,都督府下面設州。安西都護府管轄地域包括現在的新疆大部、哈薩克斯坦東部,塔吉克斯坦大部,吉爾吉斯斯坦全部,阿富汗,伊朗等國的部分地區。751年7月唐朝與阿拉伯帝國阿拔斯王朝在西域發生衝突在怛羅斯之戰大敗于阿拔斯王朝,其後唐王朝在西域的實力並未受到影響,但接踵而至的安史之亂和藩鎮割據導致唐朝無力經營西域,並自此退出對中亞霸權的爭奪。原本臣服于唐朝的中亞諸國轉而臣服于阿拔斯王朝和吐蕃王朝,伊斯蘭教文化傳入西域,改變了西域各國宗教信仰和文化成分。
8世紀中葉安史之亂發生時,吐蕃再次在之後的三十年內逐步控制了天山山脈南部的和河西走廊的廣大地區,甚至在763年洗劫了唐朝京城長安。同時,回鶻人控制漠北漠南甚至到中亞的廣大地區,包括新疆北部。9世紀中葉後,吐蕃和回鶻都衰落下來,這一地區進入混戰時期。