公元1世纪时的关系
由于行政管理网络的完成，汉朝终于成功地将西域引入贡纳体制。《后汉书》编者范晔将该体制的运转概述如下：
西域风土之载，前古未闻也。汉世张骞……班超……终能立功西遐，羁服化域。自兵威之所肃服，财赂之所怀诱，莫不献方奇，纳爱质，露顶肘行，东向而朝天子。故设戊已之官，分任其事；建都护之帅，总领其权。先驯则赏籝金而赐龟绶，后服则系头颡而衅北阙。立屯田于膏腴之野，列邮置于要害之路。驰命走驿，不绝于岁月；商胡贩客，日款于塞下。[97]
除了作者语言有一些过分的中国中心主义之外，这一特性记述说出了汉帝国与西域诸国之间关系的基本特征，特别是前汉时期（范晔叙述的分析见下文）。
后汉王朝开始时，部分地因为全神贯注于中国内部事务，部分地则由于牵涉的费用惊人，光武帝抵制了与西域之间恢复贡纳体制的诱惑。他拒绝了某些国家关于重建都护——这是汉朝贡纳制度的核心——的要求。北匈奴因此有可能重新建立对这一地区的控制，他们维持这样的控制直到公元73年中国恢复干预为止。匈奴向西域诸国中的大多数征收沉重的苛捐杂税，由于经济和军事基础的恢复，匈奴再次成为西北边境安全的严重威胁。
这个时期西域的政治地图发生了不可忽视的变化，地方政权接二连三地兴起，力争建立地区的霸权。第一个成为这样一种突出势力的政权是莎车（叶尔羌）。在前汉时期，叶尔羌是一个有16373人的中等规模的政权。后汉初年，叶尔羌一位名叫康的国王由于联合邻近国家抵抗匈奴而出名。他还为以前隶属于汉朝都护的中国官员提供保护。王莽垮台以后，这些人和他们的家庭一起在西域进退两难。这种亲汉的姿态促使光武帝赐给康以“西域大都尉”的称号，以及统治其他诸国的全权（公元29年）。
该任命不过是对一种已经存在的状态的承认，但是它赋予叶尔羌以作为西域的领袖国家行事的权威。公元33年，康的兄弟贤嗣位，贤是一个有能力但过分野心勃勃的领袖。在几年之内贤成功地使帕米尔以东几乎所有国家都从属于自己，公元41年他派一名使者前往汉朝要求给他西域都护的称号。汉朝答应了这要求，不久以后改授予“汉大将军”的荣誉称号。结果，他对汉朝越来越傲慢无礼。[98]
在以后的20年里，贤尽管受到北匈奴的攻击，事实上树立了对西域的完全统治。但是，由于向该地区的其他国家征取非常重的赋税，他削弱了自己的地位。中国人不肯卷入，于是一个包括龟兹（库车）、于阗、吐鲁番、车尔成和哈刺沙尔在内的西方政权联盟转向匈奴寻求保护。这个联盟向叶尔羌提出了严重的挑战，公元61年，于阗征服了叶尔羌并捕获了贤，从而结束了他在西域称霸的漫长时期。接着出现的是一个激烈的地区内部斗争的短暂时期，于阗、车尔成和吐鲁番以牺牲他们的软弱的邻居来争夺霸权。
可是，从西部诸国的冲突中最后得到好处的是北匈奴。他们为建立秩序和征收赋税而迅速行动起来。而且，在完全控制了西域以后，匈奴开始袭击汉朝的西部边境。从公元63年起，整个河西地区变得如此不安全，以致主要边境城市被迫紧闭城门，甚至白天也是这样。当匈奴控制西域时，西北的稳定和安全是无法恢复的。[99]
公元73年春天，统帅窦固被遣征讨匈奴。窦固从酒泉（今甘肃）北进，给予敌人以重大的打击，并把他们远远赶到巴尔库勒淖尔（蒲类海）。当返回时，他命令在哈密地区（伊吾）重建屯田。下一年，即公元74年，窦再次击溃匈奴，重新占领了吐鲁番，在这个地区建立军事殖民地有巨大的战略价值。正如范晔所正确注意到的那样，哈密特别以它的土地肥沃而知名，吐鲁番则是匈奴进入西域的主要入口。用范晔的话来说：“故汉常与匈奴争车师、伊吾，以制西域焉。”[100]这两个地区的收复使汉朝有可能重设西域都护和戊校尉，其官署分别置于库车和吐鲁番。
汉朝与西域的贡纳关系在公元77年被北匈奴和他们的卫星国再次切断，从而导致了汉朝派出第二次远征军。公元89年，统帅窦宪在外蒙古的稽洛山给予匈奴以沉重的打击。根据汉朝的官方报道，匈奴1.3万多人被杀，由20万人组成的81个匈奴部落向汉朝投降。与此同时，窦宪还派遣一支2000余名骑兵的军队向西域的匈奴根据地发起突然袭击，夺得了汉朝戍军在公元77年已从那里撤退的哈密。[101]
汉朝取得的决定性胜利，大大有助于班超在公元91年平定西域；自从公元79年的全面进攻开始时起，班超便作为一名军官在这一地区服役。当班超于公元91年到公元101年任都护时，后汉对西域的控制最为巩固。公元94年，五十余国派遣质子带着贡赋前往洛阳。
