无忌觉得虽然驱逐了太子，但隐患并没有根除，他知道，伍奢父子是忠于太子的，而且有才干，在楚国是有影响的人物，他们不死，自己的安全还是没有保证。于是，唆使平王杀伍奢父子三人。伍奢已被扣，伍尚兄弟还在城父，为了防止他们逃跑，又恐怕他们不肯就范，平王派人对伍奢说：“如果把你的两个儿子叫来，可以免死。”伍奢说：“伍尚为人忠厚、慈孝，叫他必来。伍员为人刚强暴戾，有勇有谋，并能忍辱含垢而成大事，他知道来这里会同时被扣，一定不会听命。”平王不信，派人去叫伍尚兄弟，对他们说：“你们来，我饶你们的父亲一命；不来，将你们的父亲立即斩首。”伍尚听了去郢可以救父亲，心急如火，马上准备动身。伍员说，“楚王叫我们兄弟去，并不是真正打算饶父亲不死，他是恐怕我们逃脱以后报仇，特以父亲为人质来诓骗我们。只要我们一到，他就会将我们父子同时处死。我们去，并不能救父亲。如果我们都死了，那以后哪个为我们报仇呢？不如投奔别国以待时机。”伍尚说：“我也知道即使马上去，也并不能救父亲之命，但是，既然楚王说了只要我们去就可饶父不死，而我不去，这是不孝。父亲无辜被害而不能报仇，那将说明我们太愚蠢，太无能力。你赶快走吧，我一个人去算了。”使者逮捕了伍尚，不见伍员，知其逃走，急忙追赶。伍员见使者追来，他转身挺胸站着，弯弓搭箭对着他们。伍员身材魁梧，武艺高强，特别精于箭法。使者一看不好，抱头鼠窜，狼狈而逃。伍员听说太子建在宋，就去投奔他。伍尚到都城后，果然和伍奢一道被杀。
伍子胥在去宋途中，遇到了好友申包胥。申包胥刚从国外出使回来，不知道伍家发生的事情，看到伍子胥只身独行、狼狈不堪的样子，感到很惊异。伍子胥向他简略地讲了惨遭平王迫害的经过后，咬牙切齿地说：“我一定要报仇雪耻，消灭楚国。”申包胥说：“你能消灭楚国，我能保卫楚国。你努力去干吧！请相信我们的友谊，我是不会把今日相见的事告诉别人的。”
伍子胥到宋，正遇上宋国内乱，在那里呆不下去，就和太子建一道投奔到郑。郑定公对他们很友好，招待很客气，但郑国兵力弱，不足以抗楚，郑定公建议他们到晋去求援。于是，太子建到晋。晋顷公接见之后对他说：“郑很相信你，我攻郑，你如果能够与我配合作为内应，那一定可以灭郑。灭郑以后，就把郑这块地方封给你。”太子建利令智昏，欣然允诺，回到郑国，密谋行事。但不久，机密泄露，被人告发。郑定公觉得太子建不知好歹，竟然恩将仇报，非常气愤。为了不惊动他，定公与大夫子产商量，采取了一个稳妥的办法。一日，定公请太子建到内宫参加酒宴。席间，定公单刀直入地对他说：“我好意留你住在这里避难，从没有怠慢，你为什么要与晋合谋而灭我的国家呢？”太子建企图抵赖，定公叫出揭发的人对质，太子建无言可答，表示认罪，但定公已喝令左右拿下斩首。建的随从有逃出的，把太子建被杀的事告诉伍子胥，伍子胥惊恐万分，立即带了太子建的儿子胜慌忙逃出郑城。狂奔一阵之后，来到一个偏僻的地方才住了脚，定了心。但投奔到哪里去呢？思考了一会，觉得只有吴国近年来一直与楚为敌，且国家实力较强，在那里可能有保障。于是，他不顾路途遥远，直往吴国奔去。
从郑去吴，必须经过楚国边境昭关。楚平王为了缉拿伍子胥，到处悬挂了他的画像，并标明令人羡慕的赏金。伍子胥的形象奇特，《吴越春秋》上的记载，可能有些夸张，说他“身长一丈，腰十围，眉间一尺。”所以他一到昭关，就被认出来了。伍子胥带了胜急忙快步飞逃，差一点就被官兵抓住。跑到江边，前无去路，而后面，官兵正紧迫上来。伍子胥在束手无策准备以死相拼的时候，忽然发现江边有一只小渔船，船上：有个捕鱼的老头。伍子胥忙上前哀求相救。老渔夫见义勇为，将他们渡过了江，使他们脱离了险境。伍子胥对于这样的救命恩人，当然非常感激，但身边没有什么东西可以表示自己的心意，就解下宝剑，双手捧着对老渔翁说：“这把剑是我传家之宝，价值百金，送给你老人家。”老渔翁笑着说：“楚国早就颁布了一项命令，如有人捉得伍子胥，赏给五万担粮食，并任命为大夫的官职，那岂止一把价值百金的宝剑？你还是收起留着自己用吧！”伍子胥再三拜谢而去。现传说武昌东北有解剑亭，就是当年伍子胥解剑赠渔翁的地方。
伍子胥由于风餐露宿，颠沛流离，担尽风险，还没有到吴，在路上就病倒了，加上这时盘缠用尽，不但不能住下休息治疗，连吃饭都成问题。到傈阳（江苏溧县），只好向人乞食。最后，经过千辛万苦，九死一生，才到了吴都。当时，吴王僚在位，公子光为大将。伍子胥穷途潦倒，又初来乍到，人生地不熟，如何晋见呢？他想出了一个办法。一早，他蓬头散发，打着赤脚，脸上涂着色彩，装成疯子的模样，在闹市中乞食，以引起人们的注意。果然，过路的人围着观看，但没有一个人认得他。第二天，城里的官员发现了这件事。他们经过观察，根据伍子胥的特点加以分析，断定是一个从外国逃亡来的大臣，于是，立即报告吴王僚。公子光也知道了，他心里暗暗高兴，他推测：“听说楚平王杀了大臣伍奢，伍奢的儿子伍子胥智勇双全，他为了报父之仇，一定是来吴了。”他想将伍子胥私下收留作为心腹。但吴王僚听说来了一个这样奇异的人，先召见了。经过谈话，吴王僚了解了情况，而且知道他很有才能，就任命他为大夫。
楚国边境小城锤离与吴国边境小城卑梁相邻接壤。有一天，一个锤离的女孩和一个卑梁的女孩在摘桑叶的时候，因开玩笑而发生争吵，以至打起架来。两边家里的人都赶来帮自己的孩子。这场武斗的结果，卑梁这边的那家打输了。卑梁大夫认为这是丢了本地的面子，于是派出本地军队去攻打锤离以报仇。锤离这方没有准备，打输了。楚平王听到锤离被卑梁打败，觉得有损国格，出兵占领了卑梁。吴王僚听到楚平王出兵占领了卑梁，也很生气，派公子光领兵攻楚，不但收复了卑梁，而且还占领锤离和居巢。于是，发展成为两国之间的战争。后来人们把因生活小事而导致大规模的激烈斗争称为“卑梁之衅”。伍子胥想说服吴王乘胜进兵，但公子光怕伍子胥得到吴王的宠信而不能为他所用，于是对吴王僚说：“伍子胥的父兄被楚平王杀害，他之所以劝你进攻楚国，是为了报私仇。楚国是攻不破的，我们不可能取胜。”吴王僚认为公子光讲得有道理，立即撤兵而回。伍子胥听说撤军是由于公子光的建议，心里也就明白公子光是打算夺取王位而不想远离国土。伍子胥为了避开他们之间即将发生的这场激烈斗争，辞去了大夫的职务，在吴王僚赏赐的一块不大的土地上，和胜两人耕种度日。但是，他为了要借外力报仇雪耻，在这场斗争中又不能中立。他揣度形势，认为如果协助公子光夺位成功，那上卿的职位一定是他的。于是，他开始暗地里为公子光效劳。首先，他向公子光推荐了专诸。专诸，是吴国堂邑（江苏六合县北）人。伍子胥是怎么认识他的呢？那还是从郑来吴的路上，伍子胥看见一个大汉在和人打架，凶猛异常，很多人劝解都不行。这时，忽然听到一个妇女的清秀的声音：“专诸回来！”那大汉罢手，立即转身走了。伍子胥问身旁的人：“那女人是这个大汉的什么人？”路边的人说：“这个大汉是我们这地方的勇士，力大无比，不畏强暴，好打抱不平。那女人是他的妻子，所呼专诸，是他的名字。”路人的介绍，使伍子胥产生了好奇心，便专程去拜访他。专诸很好客，两人交谈之后，甚为投机，成为挚友。专诸还特地向他解释了为什么怕老婆，他说：“屈居在一个人之下，必然是高居于万人之上。”公子光会见了专诸，见他长得目深口宽，虎腰熊背，知道是位勇士，非常高兴。从此，专诸便成了公子光的亲信。
公元前516年冬天，楚平王去世，吴王僚趁此机会于第二年春季派弟弟公子盖余和公子烛庸领兵攻楚，派叔叔季札到晋国去观察诸侯的反应和双方力量的强弱。盖余和烛庸围楚的潜城（安徽霍山县东北三十里），潜城楚军坚守不出。楚发兵救潜，截断了吴军的归路。这时，吴王僚的亲信都离开了都城，国内空虚，公子光认为时机已到，机不可失，他对专诸说：“现在不去夺取王位还等什么时候呢？”专诸同意这种看法，他说：“现在正好杀王僚。他母老儿幼，两个弟弟领兵攻楚又被断绝了归路，回来不得。现在吴国外为楚所困，内没有忠贞正直的大臣，我们如果采取行动，他是没有办法对付的。”公子光说：“我的希望完全寄托于你了，我的一切就是你的一切。”吴王僚平时戒备森严，如何才能下手呢？这一点，伍子胥早策划好了。他们知道吴王僚最喜欢吃红烧鱼。在公元前515年四月的一天，公子光请吴王僚到家里饮酒，说是找了一个最会烧鱼的厨师，经他手脍炙的鱼别有风味，特邀他去品尝。吴王僚的警惕性很高，赴宴的时候，从王宫到公子光的家门，沿途三步一岗，五步一哨，布满重兵。公子光的堂前屋后，阶台庭院，门侧席间，都是僚的亲信，手执武器，以为警卫。僚的身边，左右两名武士紧紧相随，不容任何人接近。酒宴开始，上菜的人要在堂下先搜身，再由两名手执快刀的武士左右夹着送到席上，然后再夹着退下。五道菜过后，公子光起身为王僚祝酒，站起转身时，不小心，脚扭了一下。公子光的脚本来有毛病，这一下把公子光痛得浑身发抖，额头上的汗水都冒出来了；于是对吴王僚说：“我的老病发了，需要用布紧紧包扎才能止痛，对不起，请你多坐一会，我去包扎好了就来。”公子光一步一跛地走进内室。进入内室后，向地下室飞奔而去。在隐蔽的地下室里，公子光事先埋伏了很多全副武装的勇士。公子光刚离开席间，专诸双手托着一个大盘，盘中摆着一条烧得黄灿灿的大鲤鱼，油彩夺目，热气腾腾，香气扑鼻。经过搜身，由武士挟持至席前，专诸还没有将鱼盘放好，王僚就已经拿起筷子准备伸向鱼盘了，因为他从没有看到过烧得这样精美的鱼。说时迟，那时快，专诸突然拨开鱼腹，从中抽出一把匕首直刺吴王心窝，手势十分沉重，匕首也极端锋利，穿过三层护身坚甲，直透背脊。吴王僚大叫一声，顿时气绝。这把匕首，就是著名的鱼肠剑。吴王僚的左右卫士，几乎与专诸的动作同时，刀斧齐下，将专诸砍成肉酱。公子光在地下室听到厅堂大乱，知道专诸事已告成，便带了武士杀了出来。这时，伍子胥在外也带了一百多勇士前来配合。吴王僚已死，卫队自然如丧家之犬，望风而逃。于是，公子光即位，他就是春秋后期著名的吴王阖闾。伍子胥由于出谋献策有功，被任命为行人，主要负责对外事务。不久，又有楚的伯嚭来投，被阖闾任命为大夫。盖余和烛庸攻楚被断绝了归路，在听到吴王僚被杀以后，知道没有回国的希望，便投降了。
