既然新疆「舊制」蕩然不存，那麼「新制」又是什麼呢?其實，無論是左宗棠還是劉錦棠，他們所熟悉、熱衷的「新制」就是內地各省行之久遠的行省制度。將行省制度施行於新疆，倡議於龔自珍，定議於左宗棠，成功於劉錦棠
在清代，邊疆少數民族地區通常都以「軍府制」治理。所謂「軍府制」，一般是設駐防將軍一員，主要由滿洲親貴擔任，總轄地方軍政事務，不理民政;地方民政事務由當地民族上層人士自行治理。這是從乾隆年間確定下來的制度，到了晚清，已是「日久弊生」矛盾重重了。因收復新疆而遍歷天山南北各地的湘軍總統劉錦棠感嘆地說:「舊制……蕩然無存，萬難再圖規復。」
劉錦棠(1844-1894)，字毅齋，湖南湘鄉人。他自幼隨叔父劉松山轉戰陝西、甘肅，得到陝甘總督左宗棠的器重，1870年劉松山死後便令其接統湘軍。1875年，左宗棠奉命督辦新疆軍務，移師肅州(甘肅酒泉)，令劉錦棠為總理營務。第二年，劉錦棠率湘軍進入新疆，在收復新疆之戰中連克各城，屢建功勳。1880年，左宗棠奉召進京，遺留督辦新疆軍務一職，朝廷命令由駐紮在哈密的劉錦棠繼任。
在劉錦棠等人的眼裡，既然新疆「舊制」蕩然不存，那麼「新制」又是什麼呢?其實，無論是左宗棠還是劉錦棠，他們所熟悉、熱衷的「新制」就是內地各省行之久遠的行省制度。將行省制度施行於新疆，倡議於龔自珍，定議於左宗棠，成功於劉錦棠，經歷了一個漫長的歷史過程。
朝廷最後批准了劉錦棠提出的折中方案
龔自珍提出《西域置行省議》是在1820年。那一年，清軍平定了乾隆統一新疆時亡命國外的布拉尼敦之孫張格爾的入境作亂。龔自珍針對當時的形勢提出了新疆設置行省的主張，伊犁設總督、烏魯木齊設巡撫，加強對西陲邊疆的治理。但朝廷根本沒有予以重視。半個多世紀之後，左宗棠揮軍擊退阿古柏匪徒、收復新疆之後，於1877年啟奏朝廷力陳新疆建省的迫切，同樣主張督撫並設。
對此，朝廷疑慮重重，對左宗棠的奏請遲遲未復。直到1878年，才在上諭中提出一連串的疑問:新疆「除舊有各州縣外，其餘各城改設行省，究竟合宜與否」?新疆未設州縣各處「倘置郡縣，有無可治之民?不設行省，此外有無良策」?左宗棠再次奏陳:新疆南路初復，經過招納流亡，修治水利，農民已經被安置在各地墾種，「即以目前論之，亦非無可治之民」。同年12月，清廷終於表示:「新疆議設行省，事關創始……刻下伊犁未經收還，一切建置事宜尚難遽定……俟諸事辦有眉目，然後設官分職，改設郡縣，自可收一勞永逸之效。」只是表達了同意建省的原則性意向，還須等待俄國交還伊犁之後再作最終決定。
到了《中俄伊犁條約》簽署、伊犁收回之後的l882年，新任陝甘總督譚鍾麟、業已調任兩江總督的左宗棠、繼任督辦新疆軍務的湘軍總統劉錦棠，先後啟奏朝廷，將新疆建省問題，從一般性議論推進到商討具體方案的實質性階段。
左宗棠仍然堅持總督、巡撫並設的老方案。這一方案的特點是將新疆分為兩省，不再隸屬於陝甘總督了。譚鍾麟認為，新疆人口稀少，先設道府州縣，等到人口增多了、地方富庶了，再考慮「遞設督撫」的事。他將新疆建省一事推到未來，讓人感覺到，作為陝甘總督的他是不願放棄對新疆事務管轄的。
身歷其境的劉錦棠也提出了自己的方案。他在奏摺中提出:省會設巡撫一員，駐烏魯木齊，受陝甘總督節制;下設三道:一是「舊有各州縣」的鎮迪道，將原先甘肅省鎮迪道所轄鎮西(巴里坤)、迪化(烏魯木齊)各縣，以及甘肅省安肅道所屬哈密地方合併建成;一是新設阿克蘇道，轄阿克蘇、哈喇沙爾(今焉營)、庫車、烏什等「東四城」各地;一是新設喀什噶爾道，轄喀什噶爾(喀什)、英吉沙爾、葉爾羌(今莎車)、和闐等「西四城」各地。道以下各設府、州、廳、縣。伊犁仍設將軍，只管伊犁、塔城兩處邊防，不再統轄全疆軍務;塔城增設副都統一員。
顯然，劉錦棠方案極大地照顧了譚鍾麟的職權和利益;各地設立道府而伊犁、塔城不設，同左宗棠原議相同，顯然都是為了處理好與滿洲親貴、現任伊犁將軍金順的關係。金順去職之後，伊塔道立即設置便是明證。這樣，來自上面的阻力可以減輕。果然，朝廷最後批准的是劉錦棠提出的折中方案。
新疆走在了設行省潮流的前面
l883年，劉錦棠奉旨委任了各道、府、廳、州、縣的各級官吏。他遇到了來自下面的重重阻力，主要是如何處置新任地方官員與各地伯克們的關係。
維吾爾社會實行的伯克制度由來已久。乾隆統一新疆後，曾適時地限制了伯克們的許多特權，主要是取消了伯克的世襲和殺人等權力，限定各級伯克占有「養廉田」莊園和「燕齊」農奴的數量，等等;同時又提高了各級伯克的地位和待遇，統管一方的阿奇木伯克定為三品至五品不等。早年，在龔自珍、左宗棠的建省建議中，都請求朝廷進一步限制伯克權力，因為王公伯克已經在地方上坐大，變成獨霸一方的「土皇帝」。
舊制雖然蕩然無存，昔日的伯克卻依然存在，許多伯克在清軍收復新疆的過程中作出相當的貢獻。劉錦棠在奉旨建省過程中遇到的一個實際問題便是:伯克的品級普遍高於道、府、廳、州、縣各級官吏。一縣之主的知縣，其品級同最低級的伯克相當，根本不可能號令為首的阿奇木伯克。所以他在奏摺中一再提出，只准伯克保留原品頂戴，不得干預政事。
經過劉錦棠將近兩年的籌辦，到了1884年冬，各地道、府、州、縣各級官員安排妥當，戶部終於上了奏摺，請在新疆添設巡撫、布政使等高官。於是，劉錦棠被授為新疆首任巡撫、甘肅布政使魏光燾被調任新疆布政使，建省一事始告完成。全疆軍政中心從伊犁惠遠(霍城縣境內)東移，省會設在迪化。
1885年，伊犁將軍金順奉調進京，劉錦棠立即設置伊塔道，統轄伊犁、塔城兩處地方。兩年之後，朝廷正式批准將「所有伯克名目全行裁汰」。新疆巡撫劉錦棠將昔日的伯克們分別委任為各級衙門的書吏，或承充鄉約，「專司稽查」，依舊沒有賦予他們管治地方的實權。他們也永遠失去了朝廷給予的稱作「養廉田」的莊園和名為「燕齊」的農奴。
嗣後，又經過劉錦棠及其後任諸巡撫的調整、增設，到1902年，全省共建4個道，下轄6個府、10個廳、3個州、23個縣與分縣。阿爾泰作為一個道併入新疆，成為現在新疆的一部分，那是辛亥革命以後的1919年了。
建省後，新疆全境的地方行政制度完成了一體化的進程，各族人民相互來往的種種人為限制被取消了，同時也開創了其他邊疆地區廢軍府、改行省的先河。1884年閔浙總督兼管了福建巡撫管轄的事務，福建巡撫移設台灣，稱台灣巡撫。1907年廢除了盛京、吉林、黑龍江3處將軍，改設東三省總督、吉林巡撫、黑龍江巡撫，奉天(瀋陽)巡撫一度設立後撤銷，由總督直轄。內外蒙古和西藏設立行省、簡放督撫的事也被提出議論。可見廢軍府而設行省乃是順應歷史潮流之舉，新疆走在了潮流的前面。劉錦棠作為一介武夫，能夠妥善地化解上上下下的矛盾，將新疆建省一事辦理到如此程度，也屬難能可貴。