張之洞在山西時就已經開始嚐試編練新式軍隊，在廣東期間則更進一步。不過，在張之洞編練的這些新式軍隊中，最有影響力的應該是湖北新軍。湖北新軍不僅是中國最早成型的新式軍隊，也是辛亥革命的主要參與者。
中日甲午戰爭期間，張之洞被調往兩江，代理兩江總督，主抓江蘇、安徽和江西三省的軍民政務。甲午戰後，中國慘敗，張之洞再次深刻體會到發展軍事的必要性。他在處理甲午戰爭善後事宜的過程中也作了深刻的反省，提議發展新式軍隊。他上奏朝廷，建議在江南編練一支萬人新軍，稱為“自強軍”，並提出了具體的練兵方法。
一是招募外國軍事人員來訓練中國軍隊；二是派遣中方人員出國學習新式軍隊建設；三是國內各省建立軍事學堂，開展新式軍隊教育。張之洞認為，這三者當中，能快速成軍的是第一種辦法。
當時，編練新式軍隊並不是新鮮事，湘軍、淮軍很早就開始或多或少地借鑒西方軍隊建設的經驗。但是，張之洞認為，以往學習西方軍隊，隻不過是學習他們的口號、訓練這些表麵的東西，至於戰術、指揮、行軍布陣等根本性的東西並沒有涉及，這使得所謂的新式軍隊空有其表，根本無力應對真正的新式戰爭。如果真要學習西方編練新軍，那麼，就絕不能隻學他們的皮毛，而更應該學習他們的精神。練兵不是朝夕可成的事，倉促間也許可以招募大批士兵，但是真正到了戰場上，這些不懂新式裝備的士兵毫無用處。要練兵，必須從外到內完全向西方看齊。事實上，張之洞這時在思考用西法練兵的問題時，所考慮的已不僅是武器裝備與戰術的改進，而且還有軍事製度方麵的變革。
張之洞編練自強軍的奏折很快就得到了朝廷的批準，隨即自強軍正式組建。江南自強軍是模仿德國軍製編練而成的，張之洞希望仿照德國軍製編練一支諸兵種合成的新式軍隊。1895年12月，張之洞向朝廷彙報了自強軍初步成軍的情況。自強軍仿德國軍隊的建製，設步隊8營，每營250人，分為5哨，馬隊2營，每營180騎，分為3哨；炮隊2營，每營200人，分為4哨；工程隊1營，有100人。全軍共13營，總計2860人。
這樣的規模並不大，遠沒有達到張之洞的預期，張之洞希望能夠繼續擴建到1萬人，如果沒有足夠的資金，至少不能低於5000人。
自強軍的士兵多是江蘇、安徽等地的百姓，年齡在16～20歲之間，入伍士兵必須由西醫進行體檢。為了保證兵源的素質，張之洞特別強調，堅決不能招收城市裏那些遊手好閑混日子的人。
在訓練上，張之洞聘請了35位德國軍官作為自強軍的教官，另外還挑選了一批中國軍人協助。在具體分工上，德國教官負責訓練，中國軍官負責監管。
自強軍的建設步入正軌後不久，原兩江總督劉坤一回到任上，張之洞不再代理兩江總督，回到武漢。自強軍則交給劉坤一繼續建設。
自強軍以全新的麵貌出現在世人麵前，根據梁啟超的記載，江南眾多軍隊中，沒有哪個能比得上自強軍。這支軍隊僅僅訓練了8個月，但是，士兵個個身強體健，軍容整齊劃一，槍械運用熟練，戰術動作標準規範，紀律嚴明，行動有序。看過這支軍隊訓練的西方軍事人員無不稱讚誇獎。
後世的研究者也對自強軍在中國軍事近代化過程中的意義給予了較高的評價。美國研究中國近代軍事史的專家鮑威爾認為，自強軍的建製雖然並不如張之洞所聲稱的那樣完全符合德國軍製，但已經和中國的舊式軍隊有了極大的不同，具備了很多歐洲軍隊的特點。
1896年，回到湖北的張之洞雖然離開了自強軍，但是他並沒有放棄建設新式軍隊的嚐試，他計劃用西法編練湖北護軍。這一工作是江南練兵的繼續，而且湖北護軍事實上也與江南自強軍有著直接的淵源承繼關係。
所謂“護軍”，其實就是省城衛戍部隊，負責省城的防務。張之洞在江南編練自強軍時，曾經從江南護軍中挑選1000人接受德國教官的訓練。經過半年的訓練，初見成效，這1000人具備了較高的軍事素養。當張之洞得知自己將離開兩江返回湖北後，他就開始籌劃在湖北練新軍一事。
為此，他上書朝廷，指出湖北有守衛長江的責任，而長江上盜匪時常出沒，騷擾航運，有必要加強軍隊建設，震懾盜匪。但是，湖北的財政吃緊，無力聘用外國教官。於是，張之洞就提出，將自強軍中已經練成的原江南護軍中的500人調往湖北，作為湖北練兵的模範。朝廷方麵批準了張之洞的請求。