传说越国是夏禹的后裔所建。当年，大禹治理水患来到南方，曾在会稽（今浙江绍兴市）一带活动，召集诸侯“乃大会计治国之道”，所以此地名为会稽。后来，大禹在这里“因传国政，休养万民”，他死后也安葬在会稽山。夏禹的后代少康即位时，把自己的庶子无余封在这里，以免夏禹陵庙的祭祀中断。无余就建立了国家，名为“越”。无余就是越国的始祖。
最早的吴周和越国都是楚国的附属国，地位相当。可是自从吴王寿梦叛楚以后，越国的地位也逐渐上升，成为楚国在吴国身后的重要盟国，也成为吴国的一大隐患。
公元前544年，吴王余祭为了实现攻下强楚的愿望，开始攻伐越国，消除自己的后患。那时的越国兵力弱，国土小，只是楚国的一个个小小的附属国。战争结束后，吴军俘虏了大量越军。不久之后，吴王余祭已经完全放松了对越国俘虏的警惕，让俘虏做了吴官守门人，并且负责看守吴国的船只。当吴王余祭视察船只的时候，被守船人刺杀，吴越两国自此成了“仇雠敌战之国”。
斗转星移，春去秋来，吴国在不断地强大，越国也发生了翻天覆地的变化，而且在楚国的支持下，先后从公元前537年、公元前518年两次讨伐吴国。一直到吴王阖闾时，越国已传二十余世孙，其国君是允常。
在这次吴国讨伐楚国之时，越国是吴王最大的担心。虽然在攻楚之前征服了徐国和钟吾国，在一定程度上解决了后顾之忧，但要一举拿下楚国，必然会进行旷日持久的战争，并导致双方兵力大量消耗的结果。这时候，来自越国的威胁就不得不考虑了。如果越国在吴国攻楚之时乘虚而入，后果不堪设想。这也是孙武当初难以下定攻楚决心的一大原因。
根据史书记载：“允常之时，与吴王阖间战而相怨伐。”可见，吴国与越国的战争一直不断，虽然没有经过特别惊天动地的战争，可也总是硝烟四起，战云弥漫。到了吴王阖闾时，越国这时的疆域已“南至句无（今浙江诸暨县），北至御儿（今浙江余杭县），东至于鄞（今浙江奉化县），西至于姑蔑（今浙江衢县）”方圆数百里，国都定于会稽，已蔚为南方大国。
吴王阖闾刚即位的时候，就想要重创越国，给楚国一个警告。于是，吴王阖闾命令伍子胥在姑苏（今江苏苏州市）修筑阖闾王城。这座王城的设计主要是为了防御越国。据史书记载：“越在东南，故立蛇门以制敌国”、“不开东面者，欲以绝越明也”。通过这些句子，能够很明显地感觉到吴王阖闾对越国的防备之心。
当然，阖闾认为，仅仅防御是远远不够的，而且自己已经攻下了徐同，打败了楚国。为了防止越国乘虚而入，主动出击越国已迫在眉睫。为了使自己发动战争师出有名，吴王阖闾采取先礼后兵的做法。公元前510年（吴王阖间五年）夏，吴王阖闯先派使臣去越国进行谈判，诚心地表示希望越国能够跟吴国结成联盟，共同讨伐楚国。
越王允常接见了吴国的使臣，听了吴国使臣的来意，非常气愤，坚决地说：“你们吴国不遵守与楚国地盟约，不守信用，抛弃亲如手足的楚国。现在又要与越国交往，共同讨伐亲近的友邦，鄙国不能从命。”吴国的使臣见越王允常的态度坚决，再劝无用，于是就回来向吴王阖闾复命。
吴王阖闾得知越王允常根本无意与其联盟，就准备主动出击。可是这一年，岁星降在越国的头上，按照当时观念，不利于吴国进攻越国。晋国史墨就说：“越得岁而吴伐之，必受其凶。”一边是自己的远大计划，一边是天命，究竟该怎么办？吴王阖闾犹豫了，不知该不该顺从天命。
孙武从不相信天命，他一直相信自己的能力。他认为，命运是掌握在自己手中的，事在人为。在吴王阖闾犹豫不决时，他勇敢地挺身而出，以其兵家的魄力，力劝吴王阖闾用兵，以解除将来伐楚的后顾之忧。他自信高昂地说：“自古英明的君主和贤能的将帅，之所以战而胜人，功业超众，是因为他们能首先对敌情了如指掌，这叫‘先知’。”
孙武的这些话，晓之以理，动之以情，句句都说在阖闾的心里。可是阖闾仍然害怕天谴。孙武好像看出了吴王阖闾的疑虑，继续说：“而先知不可以求神问鬼，不可以用相像的事物来比附猜测，也不可以用日月星辰运行度数去验证，必须依靠人的自身力量去努力深入地了解敌情。”
但是，吴王阖闾还是下不了攻越的决心。
有一次，吴王与孙武一起讨论一些兵法上的事情，想从中学习一些打仗用兵的战略。他问：“我军发动主要兵力进攻楚国，若越国趁我国内部空虚，突袭我国。这时，我国本土就得进行抵抗，在国内进行作战，按照将军的兵法提示，应当属于‘散地’，这种情况下作战，士卒顾家，应该坚守不出，不与敌军较量。但是如果敌军进攻我小城，掠夺我田野上的粮食牲畜，不让我们出去打柴拾草，堵塞我交通要道，待我消耗殆尽，再发动攻击，我军该如何呢？”
孙武回答：“如果敌军来我军本土侵犯，那么在他们背后肯定有许多我们的城邑。敌军由于远离本土，士兵往往把军队看做自己的家，在作战时，他们都会集中精神，全心应对，舍生忘死，勇于战斗。而我们的士兵处在本土，留恋故乡，往往不愿死战，常常抱有求生的欲望；用这样的军队排列战阵，战阵一定不会坚固；用这样的军队发动进攻，战斗一定不会获胜。因此，最好办法是结集军队，积聚粮食，储备布帛，保城备险，同时派遣轻装快速部队出奇兵切断敌军的后勤补给线：敌军挑战，我军坚守不出，敌军粮食等后勤物资运不上来，到郊外抢掠又一无所获，敌军将士就会困顿饥馁。我军借机以小利诱使敌军按照我们的预先计划行动，就可以打败敌军。”
听了孙武有理有据、合情合理的精辟分析之后，吴王阖闾的一切后顾之忧都消除了。他明白，有了孙武这样的军事奇才，何惧越国乘虚而入？何愁不能打败楚国？于是，他打消了疑虑，下达了攻击越国的命令。
吴军全线出击，杀人越国境内。这次出击是出其不意的，越国没有想到吴国会那么快就进攻自己。当得知吴王进军越国时，越国一片混乱，百姓四散逃窜，国中大臣也四散逃去，越国的将领还没有来得及组织兵力迎战，就已经被吴军包围。所以，吴国很轻易就取得了决定性的胜利。
吴王从越国班师后，唯恐越国继续组织军队来侵犯，就加紧修同城池，增强守备力量，尽量把越国北上犯吴的威胁减少到最低程度。
这次讨伐越国进行得如此顺利，与孙武的谋略是分不开的，吴王非常感激孙武的忠诚，也非常钦佩孙武的谋略和胆识。