沛公跟从项梁一个多月，项羽已经攻下襄城（河南省许昌市襄城县）回来了。项梁把各路将领全部召到薛县。听说陈王确实是死了，因而立楚国后代怀王的孙子熊心为楚王，建都盱台（ｘū ｙí，一种说法，在唐人司马贞《史记索隐》和张守节《史记正义》中有所记载，至今沿袭无异议，今江苏省盱眙县东北约25里的盱眙山麓。另一种说法，江苏省社会科学院王健教授，他认为项羽不可能进行千里奔袭，因此攻打的是距离下邳较近的相县襄城，泗水郡治相县，位于今安徽省淮北）。项梁号称武信君。呆了几个月，向北攻打亢父（位于山东省济宁市任城区喻屯镇城南张村），援救东阿（今山东省聊城市东阿县），击败了秦军。齐国军队回去了，只剩下楚军单独追击败逃之敌。另外让沛公、项羽去攻打咸阳（陕西省），屠戮了城阳（今山东省青岛市城阳区，胶东郡）。军队驻扎在濮阳县（濮阳县是东郡的治所，今河南省东北部）东边和秦军交战，打败了秦军。

秦军重新振作，守住濮阳，在城周围引水坚守。楚守撤兵去攻打定陶（山东省西南部、菏泽市中部），没有攻下。沛公和项羽向西夺取土地，到了雍丘城下（今河南杞县），和秦军交战，大败秦军，斩杀李由。又返回攻打外黄（今河南省民权县西北的内黄集宁车湾村），没有攻下。

项梁两次打败秦军，露出骄傲的神色。宋义进谏，项梁不听。秦朝给章邯增派了军队，趁着黑夜袭击项梁军队。为了防止喧哗，让士兵口里都衔着一根横木棍，结果在定陶打败了项梁的军队，项梁战死。这时，沛公和项羽正在攻打陈留（今河南省开封市祥符区陈留镇，当时属于砀郡），听说项梁已死，就带兵和吕将军一起向东进军。吕臣的军队驻扎在彭城（今江苏省徐州市）的东面，项羽的军队驻扎在彭城的西面，沛公的军队驻扎在砀县。

章邯打败了项梁的军队之后，就以为楚地的军队不值得担忧，于是渡过黄河，向北进攻赵国，大败赵军。正当这个时候，赵歇立为赵王，秦将王离在钜鹿城（为钜鹿郡的郡治，今河北省邢台市平乡县平乡镇）包围了赵歇的军队，这就是所谓的河北军。

秦二世三年（前207），楚怀王看到项梁军已被打败，害怕了，就把都城从盱台迁到彭城，把吕臣、项羽的军队合在一起由他亲自率领。任命沛公为砀郡太守，封为武安侯，统率砀郡的部队。封项羽为长安侯，号称鲁公。吕臣（西汉初年新阳侯，汉文帝六年去世，原本是陈胜的部下）担任司徒，他的父亲吕青担任令尹。

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

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

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

怀王最终没有答应项羽，而派了沛公率领大军向西去夺取土地，一路收集陈胜、项梁的散兵。沛公取道砀县到达成阳（今山东省菏泽市牡丹区胡集村东），与杠里（今山东省菏泽市牡丹区东，属于东郡的成阳县）的秦军对垒相持，结果击败了秦军的两支部队。楚军又出兵攻击王离，把王离打得大败。

沛公率兵西进，在昌邑（今山东省巨野县大谢集镇前昌邑村）与彭越（西汉初年名将、异姓诸侯王。与韩信、英布在当时被评价为“同功一体”，后世常习惯称此三人为“汉初三大名将”）相遇。于是和他一起攻打秦军，战事不利。撤兵到栗县（河南省夏邑县），正好遇到刚武侯（柴武，西汉开国功臣、将领），就把他的军队夺了过来，大约有四千人，并入了自己的军队。又与魏将皇欣（应该最后没有归刘邦）、魏申徒武蒲（也不出名）的军队合力攻打昌邑，没有攻下。沛公继续西进，经过高阳（河北省保定市东南部，隶属于巨鹿郡）。

郦食其（ｙì ｊī，秦末楚汉时期儒生，又被称作“郦生”、“狂生”，是个具有实才的辩士、谋臣。在六十多岁时投奔西征秦国的刘邦，熟识战国时期合纵连横的谋略，是中国历史上杰出的外交家）负责看管城门，他说：“各路经过此地的多了，我看只有沛公才是个德行高尚忠厚老实的人。”

于是前去求见，游说沛公。沛公当时正叉开两腿坐在床上（踞，一种坐姿，指的是臀着地，足前伸的坐姿。在古代，这种坐姿被认为是不礼貌的，因为它暴露了身体的一部分，尤其是在穿着裙装的情况下，可能会露出内裤，这在古代是极为失礼的）让两个女子给他洗脚。