2001年3月20日,新疆航空公司执管的5架图154飞机全部退役。
2002年12月31日,中国民航最后告别俄制飞机的飞行历史。
2003年1月1日,中国南航航空集团使用同一的“CZ”航班号经营国内航班,运输凭证统一使用中国南方航空股份有限公司的运输凭证三字代码784,新疆航空公司的两字代号和运输凭证三字代码在国内航班上停止使用。 3月31日起,南航集团公司国际航班和港澳航班实行统一代号、代码。 自5月3日起,南航集团飞机“红色木棉花”标识逐步替代新疆航空公司所执管飞机“天鹅明月”标识。自7月1日起,新疆航空公司飞行员、乘务员着装亦与南航集团一致。 9月1日,海南航空股份有限公司在乌鲁木齐机场建立基地。
2004年8月27日,海南航空股份有限公司新疆分公司在乌鲁木齐市正式挂牌成立。12月27日,新疆机场旅客吞吐量突破500万人次。
2005年1月1日,南航新疆公司正式加入中国南方航空股份有限公司。
2006年12月20日,乌鲁木齐国际机场年旅客吞吐量突破500万人次,迈入我国中型机场行列。
2008年3月7日,CZ6901机组成功粉碎了一起炸机未遂事件,得到党中央、国务院、国资委、民航总局的充分肯定。
2009年“7·5”事件发生后,新疆民航成立应对“7·5”事件紧急情况临时指挥部,圆满完成各类重大人员、物资的运输任务。仅7月10日,乌鲁木齐区域完成日保障502架次、塔台保障311架次、小时高峰26架次的历史最高保障纪录。
2010年3月27日,乌鲁木齐国际机场T3航站楼整体启用,可满足年旅客吞吐量1100万人次、货邮吞吐量27.5万吨、运输起降15.5万架次的运营需要。5月27日,新疆维吾尔自治区人民政府与中国南方航空集团公司签署战略合作协议,共建乌鲁木齐西部门户航空枢纽。
2011年11月22日,乌鲁木齐国际机场旅客运输量突破千万大关。
2012年6月29日,天津航空公司GS7554航班机组成功处置新疆和田“6·29”暴力恐怖劫机事件,驾驶飞机安全返航。
2013年3月12日,新疆开通乌鲁木齐到高雄包机航班,这是大陆航空公司开通的两岸最长航线,也是新疆首条直飞台湾的航线。4月1日,新疆开通直飞台湾定期航线。12月16日,乌鲁木齐国际机场分公司成立。