再回过头来看沛公，结束成阳和杠里之战后，沛公旋即向东北方向进攻昌邑（山东省巨野）。当地人彭越带一千多人投靠沛公并加入攻城战，但没能将其攻打下来。
昌邑县是秦朝设置的一所重要的军事基地之一。这里粮草充足，城墙坚固，且高度在当地那一带也是最高的。加上秦军新近连续打了胜仗，士气高昂。秦军当时的装备精良，战斗力爆表。沛公对昌邑的打法简单，采取了围而攻之的方法，却久攻不下，即便彭越带着一千多人的部队来支援，还是没能把昌邑怎样。对于彭越前来投靠。沛公非常高兴，他慷慨地封彭越为大将军。彭越也特别卖力，他带人在城西北挖了一条运粮河，为沛公的部队运输粮草等军需物品。尽管昌邑没有打下来，但彭越给沛公留下很好的印象。
这个彭越是昌邑本地人，拿今天眼光来看，妥妥的一个游击大王。在沛公与西楚霸王项羽逐鹿中原时，他在巨野泽死死拖住项羽，让这个西楚霸王来回折腾，为沛公最终打败项羽起到了非常重要的作用。
这个家伙也是一个狠角色，原先他只是巨野泽中一个渔夫。大概还兼做了其他生意，比如，领了一帮小弟占泽为王，收取过桥费之类的，偶尔也会来点硬的，反正不出点血别想从这过。
后来陈胜、吴广揭竿而起，反秦大潮如火如荼，巨野泽中许多小混混去见彭越，推举彭越带头跟着造反，一开始被彭越拒绝了。
后来经不住小混混一再要求，彭越就答应下来，然后他跟少年们约定：第二天日出的时候集合，正式举事，谁迟到就杀了谁。到第二天，迟到的人稀稀拉拉有十几个，最慢的一位中午才到。彭越说话了：“我已经一把年纪了，大家勉强要我做头领。就应该听从我的命令。昨天约好的事，迟到的要砍头，可是今天还是有这么多人迟到。总不能都杀了吧，只好把那个到得最晚的人杀了。”
开始小混混们还嘻嘻哈哈，以为彭越在说着玩的，直到这个倒霉鬼被砍了脑袋，大伙这才惊吓到了。彭越用这个人头设坛祭祀，这下所有人都乖了起来，没人敢抬头直视彭越。
彭越就是这么起家的，他杀伐果断，令行禁止，在很短时间内就把一帮小混混改变成了一支勇敢善战的游击队。然后彭越开始招兵买马、攻城略地，队伍迅扩大到了一千多人。
彭越积极协助沛公攻打昌邑，可惜没能拿下。沛公眼见昌邑久攻不下，便决定引兵西进。彭越舍不得离开家乡，便和沛公分手，回到巨野泽继续做他的山大王。
离开昌邑后，沛公回师栗邑（河南商丘）休整。在栗邑，沛公遇到了楚怀王部将武刚候，此刻武刚侯手下有四千多人。史书称沛公“夺”其军并入自己的队伍。这个武刚候名字叫陈武，应该是沛公的老相识了。当初，攻打丰邑雍齿的时候，沛公向项梁借兵五千，其中一半就是陈武带领的队伍。如今老朋友相见，自然久旱逢甘雨般的高兴。
当然，更高兴的还是沛公。不知是好言相劝还是霸王硬上弓，反正陈武的四千部队划入沛公手下。从这一个“夺”字看来，他没有经过楚王同意，将在外嘛，君命有所不受。这件事可以看出沛公翅膀硬了，或者说，西征军东奔西突，南征北战给楚怀王解决了许多头疼的问题，情况紧急，未经请示，先办了再说。沛公觉得楚怀王会理解的。
充实了力量后，沛公又联合魏将皇欣、武满的军队，第二次对昌邑的进攻。沛公仍然采取了围攻的方式。但是昌邑坚如磐石，任凭沛公怎么攻都没有拿下昌邑县城，这下沛公这边的士兵感到疲倦，粮草也快供应不上，他不得不只好退兵。