年过半百的吴起再一次沦落天涯，但幸运的是，吴起没有流浪多久，便有人带着重礼来聘请他了。
要聘请他的是楚国人，当时的楚王熊凝（史称楚悼王）。
熊凝一直以来都十分仰慕吴起的才能，非常希望自己的手下能有这样一位文武双全的人才。所以，当他听说吴起被魏国人猜忌而外出流亡时，便立马派人去请了。
正愁失业的吴起接受了熊凝的邀请，来到了楚国。
由于吴起是外人，熊凝怕一下子给予他高官会让本地的官员不服，便先把吴起任命为宛城太守，负责楚国北方的一部分军防。吴起当了一年左右的太守之后，熊凝觉得时机成熟，便力排众议，将吴起提拔到了令尹一职。
吴起终于成为一国之相了。他等这一天，已经从一个莽撞少年等到了胡子花白的老者。
但是，从吴起担任令尹的第一天起，楚国国内反对的声音就从来没有停过。首先，令尹这个职位一直以来都是楚国人担任的，而吴起一个卫国人，才来楚国一年多，就火箭式地被提拔为令尹。楚国官员就想，我本来准备混个令尹当当的，竟被吴起这个外人坏了仕途，那叫一个郁闷，所以这些人对吴起非常有看法；其次，吴起的为人一直被人们所诟病，到哪里都有一大堆人讨厌他，楚国人当然也不例外，许多人都看他非常不爽。
所有反对的浪潮都被熊凝挡住了，他信任吴起、尊敬吴起，无论大臣们如何说吴起的坏话，他都坚持自己的决定。
吴起则依然是老脾气，对于那些反对自己的人他是嗤之以鼻，报之以不屑。而且他还有一个更大的计划——在楚国变法。
变法是熊凝长期以来的想法，原因是楚国如今不变法已经是不行了。
楚国在春秋时代是当之无愧的超级霸主，但自从柏举之战后，它的国力就一直下滑，威势已经大不如前。进入战国时代，楚国因为国内的腐败问题和世袭制弊端影响，在与列国争雄之中更加力不从心。楚国人在中原事务中几乎完全丧失了话语权，诸侯们都不愿意跟从它。所以，志向宏大的熊凝下定了决心，非在楚国改革不可。
熊凝把这个重任交给了吴起，他相信吴起能办得到。
接受这样一个重大的任务，吴起心中也有些忐忑。所以在变法之前，吴起曾经两次找到了当时楚国大夫中最有声望的屈宜臼，想听听屈宜臼的意见。
没想到，屈宜臼对吴起也是不欢迎的态度。第一次去的时候，吴起居然吃了个闭门羹，屈宜臼不想见他。第二次，吴起才见到了屈宜臼。屈宜臼问他：
“你准备做些什么？”
吴起说：
“我将改革楚国的世卿爵制，把俸禄从多余的人手中转给欠缺的人，并改革军制帮助楚国争霸天下。”
屈宜臼回答说：
“我听说善于治理国家的人是不会更改国家制度的。你更改我楚国的政治制度，还要穷兵黩武去争夺霸权，这对于楚国有什么好处！你以前在鲁国和魏国改革，使他们得罪了敌国齐国和秦国，你还想让楚国陷入灾祸之中吗？我看你离死不远了。”
吴起听屈宜臼这般迂腐的陈词滥调，一下子就火起来，他说：
“难道楚国不能变革吗？”
屈宜臼答：
“不能。”
吴起愤然说道：
“我吴起尽人事，听天命。”
屈宜臼则说：
“楚国你是变更不了的，你还不如老老实实做好一个太平宰相，楚国照样能发展起来。”
吴起没有听从屈宜臼的话，不久之后，他就在熊凝的批准下颁布一整套法令，改革楚国的政治与军事。
政治法令一类的东西，罗列出来总是比较枯燥的。我这里就简单阐述一下吴起改革主要的一些措施，作为大家了解之用。
首先，吴起一把刀杀向了楚国的老贵族们。
本来，这帮老贵族们老是霸占着国家的重要职位，还世代享受着国家提供的优厚俸禄。这不仅等于是让国家花纳税人的钱养了一帮不干实事的蛀虫，而且还阻塞了平民和新贵族们的上升通道。所以，吴起就下了一个法令，宣布“使封君之子孙三世而收爵禄”，规定凡获得国家封爵的贵族，只准享受三代的优待，三代之后爵位和俸禄就要收回。而那些收回来的爵位和俸禄则被用于奖励新立功的人。这样一来，既减轻了国家的财政负担，又能调动其他人的工作积极性。
与此同时，针对楚国国土广阔，却缺乏有效开发的情况，吴起又下令停止对各地贵族的按例供给，要求他们在地方上动脑筋搞发展，自给自足，不要老是想着问中央要钱。他又命令那些在中央无所事事，整天游手好闲的贵族搬到偏远地区去，让他们负责开发那些处女地（令贵人往实广虚之地）。
接着，吴起第二把刀杀向了楚国的官场。
一直以来，楚国官场就充斥着严重的冗官问题。一个人就能干的活，非得有设立好几个人官员干。权力的重叠让许多官员捧着金饭碗，却站着茅坑不拉屎，除了扯皮踢皮球，就是卖官鬻爵。社会上走后门、递纸条、塞红包现象屡见不鲜，许多人因官致富，各种富可敌国的大贪官比比皆是。想当年拿金砖铺地的蔓成然就是个典型例子。
吴起一来，这帮昏官贪官们算是没有好日子过了。吴起花了很大的精力整顿吏治，制定了严格的官员考核制度。凡是考核不合格的、做不出政绩的官员一律辞退，把那些昏官和庸官清理出干部队伍。同时，吴起精简机构，撤销了一些重叠、多余的部门。他还严厉打击腐败，禁止走后门等行为，规范官场风气（罢无能……塞私门之请），要求每位官员都要与国家荣辱与共，专心为国效力。
最后，吴起第三把刀杀向了楚国的军队。
楚国的军队原来也充斥着不少的问题。楚军的军事制度还停留在春秋时期，士兵多是农民，缺少严格的训练。重要的职位老是由有权势的贵族占据着，一些出身低微的官兵就算立功了也很难升职。而且楚军经历柏举之战的惨败，士气低落，将士们都没信心打胜仗，上了战场就只想着逃跑。
吴起一直都是搞军事出身的，改革军队应该是他的强项。但可惜的是，因为反对的力量太大，吴起没能在楚国军队中进行大规模的改革，为楚军训练出一支像魏军武卒那样的精锐出来。他只能依照收贵族三代爵位和俸禄的做法，颁布了一道奖励军功的条例，收回旧立功者的俸禄爵位，用以奖励新立功者。但仅此一条，就为腐朽的楚军注入了不少新的活力。
吴起的能力自然不是吹的，他的变法获得了立竿见影的效果。经过改革的楚国不出几年便强大了起来。吴起小试牛刀，带兵向南征伐百越人，一直打到了苍梧（今湖南南部一带），将楚国南部的疆域扩展到了洞庭湖一带。
公元前381年，一个更能展现楚国雄风的机会来了。
当时，北方的赵国入侵卫国，卫国这么个小不点当然打不过赵国，他们便向当时强大的魏国求援。魏国人是二话不说，路见不平一声吼，该出手时就出手，立刻发兵支援，将赵军痛打了一顿。
这事儿到这里还没结束，魏国当起好汉没完了，他们又联合了齐国，打着为卫国报仇的旗号，找上赵国人的家里要“拳打镇关西”。魏齐联军攻入赵国的境内，摧毁了刚平城（今河南清丰县西南），直逼当时的赵国首都中牟。
赵国吃不消魏国人那砂锅大的拳头，便派人跑到楚国求援来了。熊凝见这是个楚国势力回归中原的好机会，便让吴起亲自挂帅前去支援。
对与老东家魏国，吴起是知根知底，他魏击手下的队伍还是自己亲手带出来的，自己还有什么好含糊的。吴起带领着楚军也来了个风风火火闯九州，直接就往魏国的土地上冲了过去。楚军在州西（位置不详）大败前来阻截的魏军，趾高气昂地横穿大梁城（今河南开封市），一直开进到了黄河岸边。吴起效仿当年楚庄王的做法，放楚军的战马饮水于黄河，向中原的诸侯展示楚国的军威。
楚军饮马黄河，使魏击不得不将赵国前线的魏齐联军撤回来，用以抵挡吴起犀利的攻势。但是魏军的将领们几乎个个都是吴起带出来的学生，他们哪里敢和吴老爷子较量。双方刚一交战，魏军就撒丫子跑了，剩下倒霉的齐军则被吴起的楚军一顿海扁，狼狈逃跑。赵国就此解围。
有楚国大哥的撑腰，赵国也跟着牛了起来。赵国随即出兵报复魏国，纵火焚毁了棘蒲城（今河北魏县南），攻占了黄城（今河南内黄县西）。