郑定公倒是相当礼遇大子建和伍子胥，让他们住在宾馆里，衣食住行都有专人照顾。也许在郑定公看来，大子建毕竟是楚平王的亲骨肉，说不定哪一天楚平王回心转意要大子建回去呢！这样的客人不能得罪，得好好供着。
但是对于大子建来说，锦衣玉食并非所求，寻回失去的地位才是最迫切的需要。他在新郑住了几个月，按捺不住寂寞，偷偷跑到晋国去见晋顷公。
这个时候的晋国，已经是日薄西山，根本没心思插手楚国的内政。晋顷公更是泥菩萨过江，自身岌岌可危，但他还是摆出大国元首的架子接见了大子建。倾听了大子建的哭诉之后，晋顷公提出一个相当坑爹的建议：“既然郑伯那么信任你，你何不回到郑国去发动一场政变？到时候晋国出兵帮助你，里应外合，把郑国给灭了，你就是郑国的主人。”
大子建怦然心动。回到郑国，他便紧锣密鼓地准备政变。郑定公发现不对劲，派人跟踪大子建的行踪，很快发现他在图谋不轨。结果大子建被抓起来砍了头，伍子胥侥幸逃脱，带着大子建的儿子熊胜偷偷离开了新郑。
以上遭遇使得伍子胥明白，要想报杀父之仇，宋国、郑国甚至晋国都靠不住，非得找吴国不可。但是去吴国的路途充满凶险，因为从河南到江苏，必须经过安徽的大部分地区，这一带，当时正是楚国的版图。而且楚国方面得知伍子胥从郑国逃出，也加强了搜查力度，严防他从眼皮底下逃脱。
诸多传奇故事发生在这一次冒险的旅途中。
在昭关（今安徽省含山县境内），伍子胥遇到了最严密的盘查。当地守将把他的画像挂在关前，过关的行人必须站到画像前，一个个接受对照检查盘问。伍子胥在附近的村落中躲了四五天，一直想不到过关的良策，急得头发都白了。正在这时，一个被称为东皋公的好心老头认出了他，将他和熊胜接到自己家里，又叫来自己的好朋友皇甫讷与伍子胥相见。
原来皇甫讷长得和伍子胥很相似，加上伍子胥一夜白头，使得皇甫讷看起来更像是正版的伍子胥。三个人商议好之后，由皇甫讷假扮伍子胥去过昭关。守关的士兵看到皇甫讷那副紧张的神情，再对照画像一看，立马认定他就是伍子胥，不由分说，将他抓了起来送到长官那里。而真正的伍子胥则趁乱跟着人群通过了昭关。
等到伍子胥走远了，东皋公才拄着拐杖慢慢悠悠地来到关里找守将，向他表示祝贺，并提出要看看伍子胥。东皋公在当地很有人望，守将和他也很熟，于是将“伍子胥”提出来。东皋公一看便笑了：“兄弟你搞错了，这个不是伍子胥，他叫皇甫讷，是糟老头我的好朋友，今天约好了去郊游，怎么被你给抓起来了呢？”
守将大吃一惊，盘问了皇甫讷几个问题，又对着画像反复看了几次，终于承认了一个他不愿意承认的事实：这个“伍子胥”是山寨版的。没办法，他只好把皇甫讷放了。
伍子胥带着熊胜继续东行，一路餐风宿露，还要躲避搜捕，艰辛自不待言。某一日来到长江边上，后有追兵，前有大江，两人只能躲在芦苇荡里，形势十分危急。恰在此时，伍子胥看到一叶扁舟，摇摇晃晃顺流而下。舟上一位渔翁，悠然自得地唱着当地的情歌：
日月昭昭乎寝已驰，与子期乎芦之漪。
芦之漪就是芦苇荡。歌词大意是，情哥哥你呀别着急，等到太阳下山月亮上来，妹妹和你相约在芦苇荡。伍子胥一听便明白了，于是在芦苇荡里一直躲到太阳落山。月亮刚刚挂上天幕，果然又听到渔翁摇着小船回来，这一次唱的是：
日已夕兮，予心忧悲；月已驰兮，何不渡为？事寖急兮，当奈何？
太阳下山了，我心悲伤；月亮高挂了，你怎么还不渡江？伍子胥带着熊胜走出来，上了渔翁的船。他朝着渔翁作了一揖，刚想说话，渔翁制止了他：“我知道你是谁，我帮你不为别的，只是同情你的遭遇。”又问：“饿了吧？”伍子胥和熊胜都不由自主地点头。从上午到天黑，他们粒米未进，何止是饿？简直是要饿晕了。渔翁说：“你们还在这里再等一下，我先给你们弄点吃的来。”
渔翁去后半个多时辰仍没有回来，伍子胥越想越不对劲，这渔翁该不会是故意使诈，诱他们出来，然后去报官了吧？他不禁打了个冷战，想要离开，却又浑身乏力，估计也走不远，干脆又回到芦苇从中躲起来。又过了一会儿，听到渔翁的声音：“芦中人啊芦中人，难道你已经离开了吗？”伍子胥不敢吱声，直到确认周围没有其他人，才又现身。
渔翁责备道：“我看你们面有饥色，才为你们回去拿食物，你们却躲了起来，难道是看不起我？”
伍子胥连忙赔礼：“在下的性命本来属于老天，现在全仗您相救，岂敢看不起！”
渔翁笑笑，奉上鱼汤泡饭。伍子胥和熊胜顾不得优雅，就坐在船头狼吞虎咽起来。渔翁荡起双桨，小船轻快地划开波浪，朝着江那边游去。等到船靠岸，伍子胥和熊胜也吃饱了。伍子胥解下随身佩带的七星宝剑送给渔翁，说：“我现在身无分文，无以为报，只有这把祖传的宝剑，价值百金，就送给您做个纪念吧！”
渔翁看都没看那宝剑，说：“我要是贪图回报的话，大王悬赏抓你，但凡活捉你的，赏谷五万石，封大夫爵，难道不比你这百金值钱？”伍子胥大为惭愧，将宝剑收起来，又问渔翁姓名。渔翁说：“就叫我渔丈人吧！”伍子胥只好再三道谢。渔翁摇船离岸，伍子胥挥手作别，又嘱咐渔翁：“请务必掩藏好我们用过的器具，免得被人发现。”
所谓用过的器具，不过就是几只陶碗，洗洗即可，哪里用得着掩藏？渔翁从伍子胥的话中听出：他还是不放心，怕我泄露他的行踪。渔翁长叹一声，道：“我这样对你，你却不相信我，罢了罢了，我就让你彻底放心吧！”说罢弄翻渔船，自沉于江中。
伍子胥心思缜密，对人缺乏信任感，由此可见一斑。但是，这个故事，很有可能是后人编造的。《吴越春秋》写到这里，接着又写道：伍子胥来到吴国，在溧阳（今江苏省南部）城内沿街乞讨，有一个女人拿出食物让他和熊胜吃饱，他又对这个女人说了同样的话，“请掩藏好餐具，不要让别人看到了。”那个女人也受不了，毅然跳江自尽。这个故事的不合理之处在于，伍子胥在楚国境内说这样的话还情有可原，到了吴国还这样说就没有任何理由了——吴国又没有悬赏要他的人头，怕什么呢？
不管怎么样，伍子胥经历了千辛万苦，最终抵达了吴国的首都，而且很快见到了吴王僚，这是毋庸置疑的。
他向吴王僚陈述了进攻楚国的诸多好处。吴王僚本来就对当年长岸之战的失利耿耿于怀，一直想找机会挽回面子，听了伍子胥的分析，未免心动。如果不是阖闾从中插一杠，伍子胥的复仇计划似乎马上就能成为现实了。
阖闾对吴王僚说：“这个人不过是想利用吴国的力量为自己报仇罢了，无缘无故讨伐楚国，对我们有什么好处？”
吴王僚被浇了一盆冷水，清醒了许多。伍子胥不由得多看了阖闾几眼，只见这个年轻人长着一张养尊处优的脸，白白净净，胡须打理得一丝不苟，穿着打扮十分华丽，一副公子哥儿的模样，很难让人联想到长岸之战中勇夺馀皇的吴军英雄。
“此人不简单。”伍子胥暗想。吴王僚确实是一个值得投靠的人物，但是相比之下，阖闾似乎更让伍子胥一见倾心。而且，从阖闾的眼神中，伍子胥还读到了一种旁人难以察觉的欲望：阖闾并不甘居于吴王僚之下，他想成为吴国的主人。
阖闾有这种欲望是不难理解的。按照吴国“兄终弟及”的传统，夷昧死后，王位本应由季札继承，但是季札拒不接受，那就应该按“父死子替”的原则，由夷昧的长子阖闾即位。没想到僚这个伯父捷足先登，以先王寿梦庶子的身份抢占了王位，阖闾怎么吞得下这口气？
没费多少思量，伍子胥便作出一个重大决定：他要成为阖闾的朋友，而不是敌人。于是话锋一转，对吴王僚说：“这位公子言之有理，您身为国君，确实不应该为了某一个人的私欲而兴兵。”
吴王僚很不悦：“你跟我说了一大通进攻楚国的好处，不就是要鼓动我讨伐楚国吗？”
伍子胥说：“国君是一国之人的国君，不能意气用事，军国大事尤其如此。如果为了下臣而兴兵，不是为君之道，请您三思。”
阖闾意味深长地看了伍子胥一眼，伍子胥的眼神和他一接触，赶紧闪开，装作若无其事的样子。这一看一闪，两个人便勾搭上了。吴王僚却没有注意到这一幕，更没有想到这次会面会给他带来灭顶之灾。
伍子胥见过吴王僚之后，便主动引退，带着熊胜过起了躬耕于野的隐居生活。当然，所谓躬耕，恐怕只是掩人耳目，每个月都有人从阖闾府上给他们送来吃用之物，日子过得还是蛮惬意的。
伍子胥给阖闾的回报是一个人。
这个人名叫专诸。据《吴越春秋》记载，伍子胥在逃亡途中，见到专诸在路上和人发生争执，对方人多势众，专诸浑然不惧，怒目圆睁，“有万人之气”，把对方逼得节节后退。然而就在这个时候，专诸的老婆倚在门口娇滴滴地唤了一声：“诸，你还不回家吃饭？”专诸立马泄了气，顾不得打人，老老实实回家吃饭。伍子胥觉得又好气又好笑，拦住他问：“你一个大男人，刚刚还在大发雷霆，怎么老婆一句话就把你弄得服服帖帖了呢？”专诸横了他一眼：“你看看我，看仔细点，我像是个傻瓜吗？不像，那你说话为什么那么粗鲁？告诉你，我是屈居一人之下，万人之上，明白吗？”伍子胥一听，满肚子不屑立马化为敬佩之情，当即向专诸赔礼道歉。专诸见伍子胥仪表堂堂，想必不是一般人，也请他到家中一叙，两人竟成莫逆之交。
自古以来怕老婆还振振有词的，专诸当属第一人。冯梦龙写《东周列国志》到这一节，也许觉得怕老婆这种事非英雄所为，便将那女人的身份改为专诸的老母。这样一来，百善孝为先，专诸头上的光环便又增加一圈了。
伍子胥将专诸引见给阖闾，阖闾天天给他吃好的喝好的，小心伺候着，甚为谦恭。如此过了一段日子，专诸终于对阖闾说：“您有什么要我做的，尽管开口吧！我一介野人，能得公子如此礼遇，便是丢掉性命也在所不惜。”
阖闾等的便是这句“在所不惜”，当下摒退左右，直截了当地告诉专诸：“吴王之位本该是我的，现在却被他人占据，我想请您杀了他，帮我夺回王位。”
阖闾说得轻松，专诸却知道这真是要拿他的性命去报答这段日子的养尊处优——吴王僚身边护卫众多，防备周密，无论刺杀成功与否，刺客活着回来的概率基本为零。他沉吟了片刻，一个大胆的计划出现在脑子里，问道：“吴王最喜欢吃什么？”
阖闾说：“鱼。”
专诸说：“那就请您派我去太湖学厨艺吧，给我三个月时间，我一定做出吴王最爱吃的鱼。”
阖闾说：“好。”
专诸从此在太湖学习厨艺，伍子胥依旧在装模作样地“躬耕”。
这期间，吴国加快了进攻楚国的步伐。
公元前519年，吴王僚亲率大军进攻楚国的州来。楚平王派令尹阳匄和司马薳（wěi）越带领楚、顿、胡、沈、蔡、陈、许七国联军救援，在钟离（今安徽省境内）与吴军相遇。大战在即，楚军统帅阳匄突然发病身亡，联军气势为之一挫。阖闾对吴王僚说：“诸侯从楚者甚众，然而都是小国，害怕楚国迫害自己，所以不得不来。现在我军在人数上比敌军少，但是我听说，胡、沈之君年少轻狂，陈国大夫年富力强却顽固不化，顿、许两国早就对楚国心怀不满，七国同赴一役却各安心思，没什么可怕的。如果集中力量先打击胡、沈、陈三国军队，必定可以将他们击溃。三国先败，其他各国就动摇了，楚军也将失去控制。请派人装出防备不周的样子引诱敌军进攻，将精兵强将留在后方给予痛击。”
吴王僚接受了阖闾的建议。
同年七月，两军在鸡父（今河南省境内）交战。吴王僚从国内调来囚犯三千人，让他们作为先锋进攻胡、沈、陈三军。
囚犯哪有什么军纪？胡乱披着盔甲，乱哄哄地冲过来，刚一接触便溃不成军，有的还知道逃跑，有的竟然傻乎乎地站在那里等死。三国军队一看，原来是个软柿子，不由得喜出望外，也乱哄哄地跑出来抓俘虏和争抢战利品。就在此时，吴军突然发动进攻，以吴王僚为中军，阖闾为右军，公子掩馀（亦为吴王寿梦之子）为左军，猛扑向三国军队。三国军队措手不及，败下阵去。
吴军却不急于抓俘虏，将败军驱赶着冲击许、蔡、顿三国阵地，这三国军队也很快崩溃。楚国人一看大势已去，走为上计，不等吴军进攻便“大奔”了。
这一战，史称鸡父之战。吴国夺取了军事重镇州来，从此“去江路而阻淮为固，扼楚咽喉为进战退守之资”，在战略上对楚国处于攻势。
且说大子建被楚平王废黜后，他的母亲也被遣返蔡国的郹（jú）阳（今河南省新蔡附近）居住。这一年八月，这个女人给吴王僚写了一封密信，请吴国人进攻郹阳，她愿意当内应开启城门。于是同年十月，阖闾带兵奔袭郹阳，将楚国存放在当地的宝器席卷一空，而且将大子建的母亲迎回了吴国。
不难看出，鸡父之战后，吴军有了深入楚国腹地作战的能力，楚国的安全受到严重威胁。司马薳越率众追击阖闾。吴军来去如风，等他赶到新蔡，阖闾已经安然返回吴国了。
薳越作为司马，防备不周，追敌不及，按照楚的法律当处死。部下劝他讨伐吴国以求获胜免死，薳越却没有了勇气，说：“国君夫人都被人抢走了，我死罪难免。如果再跑到吴国去打一次败仗，就算是多死一次都不够抵罪了。”于是自缢身亡。司马尚且如此，可见楚国在遭受了连续两次重大打击之后，上下都弥漫在一种失败的情绪之中，士气萎靡不振。
阳匄死后，囊瓦接任令尹。囊瓦是公子贞的孙子（公子贞是楚共王的弟弟，曾在楚共王和楚康王年间担任令尹），这位贵胄之后生得玉树临风，却是外强中干。据说楚灵王年间，晏婴出访楚国，囊瓦当时担任楚灵王的戎车车夫，曾向晏婴挑衅：“我听说王侯将相，都有魁梧俊美之相，因而能立功当代，留名后世。您身长五尺，力不能缚鸡，不觉得羞愧吗？”晏婴回答：“当年侨如身长九尺，而被鲁国所杀；南宫长万神力盖世，却死于宋国。你长得那么高大，还不是只能为楚王御马吗？”将囊瓦弄了个大红脸。
囊瓦上台的第一件事便是加固郢都的城墙，这也是时势所逼——谁知道那些不要命的吴国人会不会突然杀到郢都来呢？但是左司马沈尹戌对囊瓦的未雨绸缪持批评意见：“子常（囊瓦字子常）这样做，不是保护郢都，而是灭亡郢都。如果人不能卫国，就算城墙加得再高也是无益。现在关键任务是提振士气，克服对吴国的恐惧之心，这个时候修城，不是加重了大家的恐惧么？”
囊瓦小心翼翼，楚平王却又过于冲动。公元前518年十月，楚平王亲率水军巡视吴楚边境，想为去年的两次失败挽回一点面子。沈尹戌又提出批评：“这一次行动，楚国必定失地。不安抚百姓而滥用民力，吴国动态不明而轻举妄动。如果吴军发动突袭，又没有应变的预案，怎么能够不吃亏？”
楚平王不理会这些，在豫章（今江西省境内）接受了越国人的犒劳后才返回楚国。吴国人趁其不备，突然袭击了钟离和居巢（今安微省境内），将这两座城市焚为灰烬。
