公元前207年，楚怀王看到项梁军已被打败，害怕了，就把都城从盱眙迁到彭城，把吕臣、项羽的军队合在一起由他亲自率领。任命刘邦为砀郡太守，封为武安侯，统率砀郡的部队。封项羽为长安侯，号称鲁公。吕臣担任司徒，他的父亲吕青担任令尹。

前文说过，赵国几次请求援救，怀王就任命宋义为上将军，项羽为次将，范增为末将，向北进兵救赵；命令沛公向西攻取土地，进军关中。并和诸将相约，谁先进入函谷关平定关中，就让谁在关中做王。

这时候，秦军强大，常常乘着胜利的威势追击败逃之敌，诸将中没有人认为先入关是有利的事。只有项羽恨秦军打败了项梁的军队，很激愤，愿意和沛公一起西进入关。

怀王手下的老将们都说：“项羽这个人敏捷勇猛，却又奸猾伤人。项羽曾经攻下襄城，那里的军民没有一个活下来，都被他活埋了。凡是他经过的地方，没有不被毁灭的。再说，多次进攻，先前陈王、项梁都被打败了，不如改派忠厚老实的人，实行仁义，率军西进，向秦地的父老兄弟讲明道理。秦地父老兄弟因为他们的君主暴虐而受苦已经很久了，现在如果真的能有位忠厚老实的人前去，不欺压百姓，才会使秦地降服。项羽只是敏捷勇猛，不能派他去。现在只有沛公一向忠厚老实，可以派他去。”

怀王最终没有答应项羽，而派了刘邦率领大军向西去夺取土地，一路收集陈胜、项梁的散兵。沛公取道砀县到达成阳，与杠里的秦军对垒相持，结果击败了秦军的两支部队。楚军又出兵攻击秦将王离，把王离打得大败。

刘邦率兵西进，在昌邑与彭越相遇。

彭越是昌邑人，原来常在巨野湖泽中打鱼，伙同一帮人做强盗，有点类似梁山泊上的人物。

陈胜、项梁揭竿而起，有的年轻人就对彭越说：“大哥，很多豪杰都树起旗号反了；凭您的能耐，自然不比他们差，咱们也效仿他们那样干吧！”

彭越却异常冷静：“现在两条龙刚刚斗起来，还是再等等吧！”

过了一年多，泽中年轻人聚集了一百多，前去追随彭越，请他做首领。彭越起先还拒绝，并且严正声明：我不愿跟你们一块儿干。可还是经不住这些人的请求，最终答应了，跟他们约好第二天太阳出来时集合，迟到的就杀头。

第二天太阳出来的时候，迟到的就有十几个，更有甚者，直到中午才来。

当时，彭越很抱歉地说：“我老了，你们执意要我当首领，我推辞不得。现在，约定好的时间却有这么多人迟到，不能都杀头；只杀最后来的一个人。”于是就命令执掌处罚的人将最后一位迟到者杀掉。

大家都嘻嘻哈哈笑着，何必这样呢，今后不敢再迟到就是了。然而，彭越却不为所动，直接将最后到的那个人杀了。然后设置土坛，用人头祭奠，号令所属众人。众人都大为震惊，没有谁敢抬头看他。

彭越由此树立了威信，开始领着大家四处夺取土地，收集诸侯逃散的士兵，积少成多，队伍的实力迅速壮大起来。

昔日刘邦从砀北进击昌邑时，彭越曾率队相助。昌邑没攻下，刘邦带兵西进，彭越也率领他的部队留在巨野泽中。等到项羽入关中封立诸侯，却对彭越视而不见。当时彭越部队因收编魏国的散兵游勇，也已发展到一万多人，可一直没编入正规军。

等到齐王田荣反楚的时候，彭越大显身手，打败了楚军。后来刘邦挟魏王豹等五路诸侯共同攻楚，彭越就率三万多人在外黄归附了他。彭越在攻下魏地十多个城邑后，急于想立魏国的后代；而魏豹是前任魏王魏咎的堂弟，是真正的魏国后代，刘邦便任命彭越为魏国相国，专掌兵权，平定梁地。