屡试不中，袁世凯慷慨陈词：“大丈夫当效命疆场，安内攘外，乌能龌龊久困笔砚间，自误光阴耶！”决定投身军旅，以求发迹。
1881年，一个叫吴长庆的人在山东登州主持海防。袁世凯的养父袁保庆是吴长庆父亲的救命恩人，吴长庆与袁保庆也是八拜之交。吴长庆为了报答袁保庆，便写信给袁世凯，要他去山东学习军旅之事。袁世凯接信之后，真是喜从天降，欣喜万分，便起程到了吴长庆军中，开始他的军旅生涯，结束了浪荡不羁的纨绔子弟生活。
袁世凯在军队当中，因为与吴长庆的特殊关系，很受重用。吴长庆对袁世凯十分信任，处处关怀，让其帮办文案之事。
1882年7月，清政府的蕃邦朝鲜发生了“壬午兵变”，朝鲜请求清政府出兵救援。清政府马上派吴长庆率六营士兵，在水师提督丁汝昌率领的三艘军舰护卫之下，东渡朝鲜。袁世凯被吴长庆委派负责军需，并勘探行军路线。袁世凯欣喜万分，他觉着自己到朝鲜可以建功立业，大出风头，加上可以看到异国风光，这一切对于年轻的袁世凯来说，无疑具有极大的吸引力。况且，出国征战，对于喜骑马试剑的袁世凯来说，更合其性格和胃口。这次出征朝鲜，也为袁世凯以后的升官发财创造了良好的契机。
说来事也凑巧，吴长庆率军乘船抵达朝鲜的南洋港后，命令一个营作为先锋，准备第二天登陆。但这个营的长官说士兵不习航海，多数晕船，请求稍缓时日。吴长庆大怒，马上撤了那个营的长官之职，让袁世凯代理。袁世凯代理营长官之职后，表现得十分机智果断，在二小时之内把一切布置就绪，吴长庆大加夸奖。后来，清军登陆之后，因为纪律松弛，奸淫妇女、抢掠财物之事，时有发生。袁世凯此时便使出了铁血手腕，斩杀了七个带头的人，起到了杀鸡儆猴的作用。袁世凯的聪明果断，令吴长庆刮目相看，便让其总理前敌营务处，特意负责整顿军纪事宜。由于有了吴长庆的支持，袁世凯在执法时不徇私枉法，很快惩治了犯法的士兵，查办了管兵不严的军官，从此军队的纪律得到了根本上的改观。吴长庆对袁世凯更加赏识，袁世凯也因此在军队中树立了自己的威信，就连吴长庆的一些亲近故旧军官，也畏惧袁世凯三分。
一切就绪之后，清军向朝鲜叛军发起攻击。袁世凯也参加了作战行动，并率领清军杀死几十名叛军。因为参加兵变的人员缺乏统一领导，全是乌合之众，因此，在清军的猛烈进攻下，很快就溃败了，这场叛乱就这样迅速平息了。朝鲜国王李熙为感谢清军，设宴招待吴长庆等人，袁世凯也受到李熙的接见。对于袁世凯的表现，吴长庆给予了很高评价。他称赞袁世凯“治军严肃，调度有方，争先攻剿，尤为奋勇”，并上报李鸿章为其请功。不久，在李鸿章的奏保之下，清政府赐袁世凯花翎，并被提升为同知。
朝鲜的“壬午兵变”平息之后，清政府出于对朝鲜局势的考虑，让吴长庆驻军朝鲜，袁世凯也留了下来。自此，袁世凯成为吴长庆麾下的一员猛将，年仅24岁。这时，朝鲜国王李熙吸取兵变的教训，准备训练新军，拟请袁世凯为军事顾问。李熙亲自来到吴长庆的军营拜访，求借袁世凯。起先，吴长庆不答应，但在李熙的再三恳求之下，吴长庆只答应袁世凯替朝鲜兼练新军。袁世凯接受了朝鲜国王李熙的要求之后，便依据清军的规格草订制度，编选壮丁，又鉴于朝鲜王室地位的孱弱，他便先建立国王的亲卫军，然后组织镇抚军，以加强政府的地位。李熙对于袁世凯的所有措施感到极为满意，便敦请袁世凯移居朝鲜的三军府居住，以便就近指挥和督练朝鲜军队。
起初，吴长庆对袁世凯关怀备至，十分信任。袁世凯也感恩戴德，常常在家信中说：“吴帅相待日见加优，谏行言听，可感之至。”但随着袁世凯声望鹊起，日益活跃，吴长庆便与其关系日渐疏远，甚至怀疑袁世凯不安好心，想夺自己的权。吴长庆的冷待，使得袁世凯十分寒心，觉得无望再升迁，前途十分渺茫，因此想要回到国内，以摆脱此困境。其堂叔袁保龄与李鸿章之婿张佩纶过从甚密。因此，袁世凯便通过这层关系写信给张佩纶，并送了八件难得的古物，想在李鸿章的北洋署内谋一位置。
1884年5月，清政府令李鸿章加强东北边防。张佩纶便和袁保龄商量，让李鸿章把吴长庆调回国内，主持东北边防。因此，李鸿章奏请朝廷让吴长庆率三营兵马回国，其余三营仍留驻朝鲜，以记名提督吴兆有统带，袁世凯总理营务处并办理朝鲜防务。如此一来，袁世凯实际上成了驻朝鲜清军的最高统帅，成为一个手握军权的实力人物。一朝大权在握，袁世凯便飞扬跋扈起来，以为自己有李鸿章作为靠山，从此便可青云直上。但朝鲜的局势并不稳定，内部分为开化、保守两派。保守派以闵氏为首，亲近中国，得到吴长庆、袁世凯的支持。开化派以金玉均为首，亲日，企图依靠日本推翻保守派的统治。中法战争爆发后，金玉均等认为此时中国自顾不暇，便寻机刺杀保守派首领，日本公使率日军100余人支持开化派，冲入朝鲜王宫，捕杀保守派。袁世凯会同吴兆有要求李鸿章派军舰赴朝，准备举兵，保守派首领金允植等也请求清军援助，袁世凯遂自行决定派兵入宫，在朝鲜人民的支援下，攻入日军占领的朝鲜王宫，日军自焚使馆，狼狈逃走。保守派重新掌权。
事变后，袁世凯亲率淮军一营驻守王宫，以“监国大臣”自居。他给李鸿章写了一篇长达数千言的报告，认为“莫如趁此民心尚知感服中朝，即派大员，设立监国，统率重兵，内治外交，均为代理，则此机不可失也”。然而，此时日本政府致函清政府，反咬一口，指控袁世凯在“甲申政变”中肆意挑衅，引起中日冲突。清政府不明真相，便命李鸿章和吴大澂负责处理。经过商议，决定由吴大澂、续昌二人赴朝查办袁世凯。吴大澂等抵朝鲜后，袁世凯将事变经过书面呈报，并当面辩解。吴、续二人了解真相之后，未责备袁世凯，反夸奖他劳苦功高。但恐袁世凯继续住在王宫引起日本人猜疑，又寻找别的什么托辞，便令其撤出，驻回清军大营。前后两件事情对袁世凯的打击，使他心灰意冷。就在袁世凯处境不妙之时，其养母牛氏闻知朝廷派人到朝鲜查办袁世凯，吓得卧床不起。因此，袁世凯以探母为由，向吴大澂告假回国。
吴大澂、续昌回京复命时，对李鸿章说袁世凯乃奇才，可大用。此时，袁世凯还在天津，还没回老家探母，李鸿章便召见了袁世凯，让他仍回朝鲜任职，但袁世凯坚持回家探母，没有答应。后来，袁世凯又以驻朝鲜总理交涉通商事宜的身份出使朝鲜。在出使朝鲜的这九年时间里袁世凯初步在中外政治舞台上发挥作用。但由于日本不断增加驻朝兵力，到1894年时，已超过驻朝清军人数，日本企图霸占朝鲜的野心已充分暴露，并把枪口对准清军，战争一触即发，在这种情况下，袁世凯仓皇逃归。袁世凯逃归不久，日本海军在牙山口外海面忽然袭击中国军舰和运兵船只，不宣而战，挑起战争。清政府被迫对日宣战，中日甲午战争爆发。
甲午战败之后，1895年2月，清政府派李鸿章前往日本办理投降事宜。这时的李鸿章已成为众矢之的，但袁世凯却对他恭恭敬敬。李鸿章在马关遇刺之时，袁世凯马上拍电报表示慰问。李鸿章与日本签订《马关条约》之后，舆论哗然。正在北京参加应试的举人康有为等人上书朝廷，要求废除和约，进行改良，挽救民族危亡，这就是历史上有名的“公车上书”。甚至有的人提出杀李鸿章以谢天下，废约再战。李鸿章回国之后，呆在天津的家里不敢出来。袁世凯不避嫌疑，特地赴天津谒拜李鸿章，李鸿章夸奖了袁世凯一番，并答应保举袁世凯进一步升迁。如此，袁世凯在李鸿章的羽翼之下步步高升，成为一个政治宠儿。