《辛丑条约》签订后，尽管俄军始终赖在东北不走，清政府仍决心重建东北军政。考虑到东北的军警力量早已瓦解，清政府决定对未经官方认证的地方武装详加勘验；对声誉良好、有改造前景的保险队收为己用，对劣迹斑斑的保险队，则视同土匪，严加剿灭。
张作霖的保险队被纳入招抚名单，由官府做进一步考察。张作霖决心改弦更张，彻底洗白，积极协助官府剿匪。1902年10月，受盛京将军密令，张作霖率队伍前往围剿有400多人马的海沙子匪帮。张作霖身先士卒，身中一枪，轻伤不下火线。经一天一夜血战，全歼海沙子匪帮，盛京将军论功行赏，当月就命新民府对张作霖保险队正式收编，并由对张作霖并不熟悉的新民府官员段有恒充当保人。张作霖感念段有恒知遇之恩，毕生以父子之礼事之。段有恒本人声名不显，他的儿子是袁世凯的亲信重臣，皖系领袖段祺瑞，则是段有恒的侄孙。
1902年11月9日，新民府知府增韫亲自前往八角台主持收编，任命张作霖为“新民府巡警前营马队帮带”， 即骑兵副营长并向张作霖和弟兄们强调国法军规。被官府收编后，张作霖所部作战勇敢，剿匪坚决；尤其是，张作霖重视军纪，颇得民心。1903年7月，新民府将张作霖部与新民街巡捕队合并为“新民府巡防马步游击队”，张作霖升任管带，即营长。”新民府巡防马步游击队”的性质属官府认证的地方武装，军饷由本地筹措，上交官府后，再由官府后向部队发放。1904年春，因当地筹饷困难，经增韫向盛京将军，张作霖部被正式列入朝廷统辖的正规军。
1904年2月，日俄战争爆发。日俄双方都大量征召、收编土匪、保险队为己方效力。清政府名为“中立”，其真实心态，乃是依靠日本力量，将霸占东北已4年之久的俄军彻底驱逐出境。从日俄双方史料记载来看，甚至有大量清军直接参与对俄作战。。冯麟阁“大团”和辽西巨匪杜立三都积极参与对俄作战；本受沙俄扶持的金寿山保险队见风使舵，也配合日军作战。
经旅顺会战、奉天大会战和对马海战三场大战，沙俄战败，撤出东北。1905年12月22日《中日会议东三省事宜正约》签订之后，除在旅大租借地驻扎之关东军和在南满铁路附属地驻扎之满铁守备队，日军也撤出东北其余区域。以此为契机，清政府在东北进一步施行军政改革，以图加强对东北的管理和控制。
经第一次中日战争和庚子国难，清政府在东北的驻军已几乎全部土崩瓦解。1905年，兼管留都兵部的盛京将军赵尔巽重新编练马步46营，驻扎于盛京将军辖地各处。1906年年底，赵尔巽又将盛京将军辖地各处驻军编成八路巡防营，张作霖所部五营被编为“右路巡防营”；冯德麟所部被编为“左路巡防营”；其他各路巡防营，也大多与保险队之类的地方武装渊源颇深。
1907年，清政府制定《东三省督抚办事要纲》和《官职章程》，裁撤盛京将军辖地、吉林将军辖地和黑龙江将军辖地，建奉天省、吉林省和黑龙江省，盛京将军改为东三省总督，吉林将军和黑龙江将军改为吉林巡抚和黑龙江巡抚，另增设奉天巡抚。废除旗民分治，将军所属各八旗副都统一并裁撤，所领旗务均归行省管辖。在东北正式撤将军、设行省之前的1905年，经盛京将军赵尔巽奏请，清政府已经以“事权不专”、“百弊丛生”为由，裁撤留都盛京五部。
东三省总督徐世昌励精图治，除从关内调入新军并在东北就地组建新军外，还对巡防营等旧军大力整顿，并组织力量，继续围剿各路土匪。辽西巨匪杜立三匪帮在日俄战争中积极参战，乘机将势力做大，此时“兵力”已达千人之多。他在奉天辽中县青麻坎修筑炮台，设卡勒索，自称“马上皇帝””。从史料记载来看，因“辖区”内辽河多年泛滥成灾，杜立三曾组织维修辽河河道，让台安和辽中一带几十里饱受水患之苦的洼地成为沃野良田。但杜立三贪婪、短视，对“辖区”内民众压榨极重；还多次袭击清军，抢夺军火。如果说沙俄霸占东北期间，杜立三匪帮尚有维持地方的一面，此时天下初安，政府勉励整顿地方军政，杜立三匪帮的存在已再难被各方容忍。
前后几次进剿都大败而归，徐世昌密令下属殷鸿寿与张作霖商议对策。张作霖和张景惠、张作相、汤玉麟商议后，决定设计诱杀杜立三。张作霖先向杜立三致贺信，佯称东三省总督府派员到新民府对其招抚，请其速来新民府与有司洽商招抚和晋升事宜。杜立三收信后担心是计，拒绝前往。张作霖又哄骗杜立三的同宗叔父杜泮林出面相邀，杜立三信以为真，带着13名随身护卫前来新民府赴会。临行时杜立三令留守土匪随时待命，如听到风吹草动，就随时驰援；又在青麻坎到新民途中安排四个哨所，每所十名骑匪，往来探听消息，快马传报。张作霖闻讯大喜，做了更加周密的布置。他预先令张景惠率骑兵500人潜回八角台隐蔽，但等杜立三出发后，立刻进驻青麻坎附近的新开河镇，随时准备突击青麻坎；张作霖另遣大批骑兵暗中监视杜立三在路上布置的四处哨所，一旦听闻杜立三到达新民府，就立即予以消灭。在新民府，张作霖精心设下一场鸿门宴。
1907年6月6日，杜立三一行14人到得新民府城郊，就被张作霖派人接入城内，安排进早已被便衣军警接管的客栈。随即，张作霖只带着两名护卫前来客栈设宴接风，让杜立三彻底放松警惕。宴后，张作霖请杜立三移步到新民府衙商议招安事宜，杜立三只带了两名保镖随同前往。在府衙院内，伏兵四起，杜立三死于乱刀之下。与此同时，在八角台隐蔽待命多时的张景惠所部突袭青麻坎成功，杜立三匪帮就此灰飞烟灭。1907年8月17日，清政府以剿灭“奉天匪首杜立三”之功，授予张作霖“蓝翎都司衔，以游击尽先补用”，不久提升张作霖为奉天巡防营前路统领。
除对东北图谋已久，沙俄也从未放弃对内外蒙古的野心。1900年9月，内蒙科尔沁右翼后旗爆发"刚保与桑保之乱"。此时正值沙俄入侵东北，驻扎于齐齐哈尔一带的俄军闻讯后立即前往镇压，随即在该旗赖下不走。1901年，沙俄派军官格罗莫夫深入内蒙哲里木盟进行特务活动，刺探蒙古王公的政治动向，并寻找和培植代理人。哲里木盟扎萨克图旗的札萨克郡王乌泰此前因胡作非为欠下巨额债务，濒临破产，此时又刚被清政府削去哲里木盟副盟长一职。格罗莫夫与败类乌泰一拍即合，立刻把乌泰收买为里通外国的内奸。当年冬天，因为和扎萨克图旗协理台吉巴图济尔噶勒等人发生内讧，乌泰竟带着旗印窜逃到哈尔滨向沙俄“总督”寻求“避难”。同一时期，郭尔罗斯后旗、敖汉旗等旗的蒙古王公，也被沙俄成功收买。1907年，日俄秘密订立《日俄密约》，擅自在东北和内蒙划分势力范围，将内蒙郭尔罗斯后旗、杜尔伯特旗、扎赉特旗、镇国公旗、札萨克图旗划入沙俄势力范围。《日俄密约》签订后，沙俄在哲里木盟大肆开展特务和颠覆活动。
满清对蒙古王公日益增长的离心倾向早有察觉，也采取很多举措积极应对。1904年，御史姚锡光奏《请拣派大员专办内蒙垦务》，建议在内蒙垦荒实边。清政府诏令直隶总督、东三省总督、察哈尔都统和热河都统会商此事。东三省总督徐世昌建议划昭乌达盟之巴林二旗、阿鲁科尔沁一旗、扎鲁特二旗，锡林郭勒盟之乌珠穆沁二旗、浩齐特左翼一旗和哲里木盟之图什业图、达尔罕等旗作为垦荒范围统筹兴办，并重申“垦务之宗旨在殖民固边，而不在于筹款”。清政府斟酌良久，令察哈尔都统和热河都统负责察、热辖区垦荒事宜，由徐世昌对东三省所属蒙古盟旗“通盘筹画”，派员督办。
1908年，徐世昌在奉天设“东三省蒙务局”，统筹哲里木十旗蒙务，以“扶殖蒙旗，隐杜交涉，兴利实边”为宗旨，“规画全盟兴革”。“东三省蒙务局”迅速拿出方案，计划在哲里木盟铺设电线，敷设铁路，开办实业，添设官吏，加强守备，移民实边；徐世昌又奏请开放达尔罕旗荒地。尽管达尔罕亲王 “多方阻挠，藉口于有碍蒙民生计”，清政府仍于1909年年2月下旨，“著该督抚妥筹勘放”。东三省蒙务局的“筹蒙”计划随即正式付诸实施。
陶克陶胡是哲里木盟郭尔罗斯前旗一名所谓的没落贵族，其家世自称可追溯至铁木真的二弟哈撒儿，实则早已世代务农为生。多年来沙俄在哲里木盟大肆从事颠覆活动，陶克陶胡早已接受沙俄收买。此时清政府“筹蒙”，大量关内汉民前来垦荒，引起当地蒙古牧民不满，陶克陶胡沙俄特务指示，借机煽动民族仇恨，以“抗垦”为名拉起队伍深入奉天、吉林境内烧杀抢掠，无恶不作。
陶克陶胡之“抗垦”队伍时称“蒙匪”，实则假托土匪之名，行里通外国之实，直接服务于沙俄对满蒙的侵略目的。见张勋、倪嗣冲、赵佣等部清军先后进剿失利，徐世昌改派张作霖、冯德麟和马龙潭率所部巡防营前往洮南剿匪。出征前，徐世昌把奉天八路巡防营重新整编为中、前、左、右、后五路巡防营，以张作霖为前路统领，除原由张景惠、张作相、汤玉麟等统领的5营兵马，另将驻扎于洮南的孙烈臣部也划归张作霖部建制。数年间，张作霖和其他各部始终坚持在剿匪前线，在草原和荒漠中千里奔波，露宿寒林，捧雪为食。1908年6月，张作霖率所部在蒙匪老巢龙王庙大败蒙匪，击毙匪首之一巴特尔；1909年春又将匪首白音达赉击毙；到1910年4月，终于歼灭匪首陶克陶胡率领的蒙匪主力，陶克陶胡仅带残匪45人越境叛逃沙俄。徐世昌称，洮南剿匪之胜利”实非寻常剿匪之功可比。”
经洮南剿匪，不论张作霖个人的威望与影响力，还是张作霖所部之战斗力和凝聚力，都发生翻天覆地的改变。徐世昌先后将前路巡防营张作霖部、后路巡防营吴俊陞部、左路巡防营冯德麟部和右路巡防营马龙潭部派上洮南剿匪前线，各部公认以张作霖部战斗力最强、战功最高。吴俊陞、马龙潭年龄、资历都在张作霖之上，而且行伍出身，身世清白，没有“绿林”背景；洮南剿匪期间刚被划归张作霖节制的孙烈臣本与张作霖平级，曾是前任盛京将军增琪的警卫员出身，对增琪还有救命之恩。出师之前，吴俊陞、马龙潭、孙烈臣三人不服，对张作霖颇多不敬之词。几年征战，三人都为张作霖的义气和忠勇折服，不仅彼此皆为生死与共的兄弟，还心甘情愿以张作霖为先。剿匪期间，大家在洮南关帝庙义结金兰，八人叙年齿排行，分别是右路统领马龙潭、后路统领吴俊陞、左路统领冯德麟、前路马二营帮带汤玉麟、前路马三营帮带张景惠、前路马四营帮带孙烈臣、前路统领张作霖、前路马一营帮带张作相。此次结拜，预示着属于奉系集团的时代即将到来。
清末陆军中新军、旧军并存。第一次中日战争战败后，清政府痛定思痛，令湖广总督张之洞、直隶提督聂士成、温处道袁世凯开始编练新式陆军，“习洋枪，学西法”，称“新建陆军”，通称“新军”。1903年12月4日，清政府接受袁世凯的建议，设练兵处，统一领导编练新军事宜，并在各省设督练处，训练、统辖全省新军。到武昌起义前夕，各省共编练新军14镇、18协、4标，连同禁卫军2协，共20多万人，采用日本操法训练，全部装备近代武器，士兵文化程度较高，军官大多毕业于新式讲武堂，具备近代军事知识技能，战斗力远较八旗、绿营、巡防营为高，成为清末陆军的主力。
武昌起义前夕，奉天也是新军、旧军并存。驻扎在奉天省的新军包括驻扎于奉天、新民一带的陆军第20镇和驻扎在奉天大北关北大营的陆军第2混成协。第20镇统制张绍曾和第2混成协协统蓝天蔚都毕业于日本陆军士官学校，为陆士第一期炮兵科同学。1907年年初，张绍曾、蓝天蔚和两人的另一位陆士同学吴禄贞一起被新任东三省总督徐世昌调往奉天任职。当年4月，宋教仁以创办实业为名，来东北为同盟会发展会员，并在丹东成立同盟会辽东支部，张绍曾、吴禄贞、蓝天蔚均秘密加入同盟会，倾向革命。旧军为张作霖、冯德麟、吴俊陞、马龙潭等诸路巡防营，其中张作霖始终率前路巡防营留驻洮南，弹压地方，避免蒙匪死灰复燃。彼时关内各省的防务基本被新军把持，唯有奉天旧军以洮南剿匪中锻炼出的战斗力为后盾，可与新军分庭抗礼。
