大约在刘邦重夺丰邑的半年前，也就是秦二世二年腊月，陈胜军队连败于秦大将章邯，眼看形势不妙，他的车夫庄贾杀了陈胜作为降秦的投名状，张楚政权灭亡，仅存续了半年。
当时，一名叫范增的谋士前往项梁处，说道：“陈胜失败是必然的。秦灭六国，楚国最冤。当初楚怀王（熊槐）到秦国后未能返回，楚人至今还很怜惜他。所以才有‘楚虽三户，亡秦必楚‘的说法。如今陈胜率先反秦，不拥立楚王之后，必然是不长久的。阁下自江东起兵，有众多追随者，原因就是项家世代皆为楚将，大家都期望您能恢复楚国。”
楚是战国时期面积最大、人口最多的诸侯国，国力十分强盛。《史记·苏秦列传》这样描述楚国：“地方五千余里，带甲百万，车千乗，骑万匹，粟支十年，此霸王之资也”。楚国本可与秦国一争高下，但楚怀王两次被张仪设计欺骗，致使国力大损，又被秦昭襄王扣押为人质直至客死秦国。所以楚人对秦人有天然的仇恨，也都抱有复国之志。以楚为号反秦，会大大增强这支力量的群众基础。
这与秦嘉立景驹之策略不谋而合，只是他没有选择楚王之后，再加上实力确实不如项梁，最终身败名裂。
项梁听从了范增的建议，从民间找到了正在牧羊的楚怀王之孙熊心。六月，刘邦在薛县与项梁共立熊心为义帝，仍名为楚怀王，定都盱台(xūyú)，以利号召天下。这里注意，前面刘邦搭上了项氏集团，这里又与其共立义帝，便有了拥立之功。这为后面刘邦封侯奠定了基础。
同月，章邯围魏王魏咎于临济，魏咎向项梁、田儋求援。章邯夜里发动攻势，大破楚、齐联军，田儋被杀。为了避免百姓受苦，魏咎投降章邯后自杀。田荣收拢田儋剩余的人马向东阿方向逃去。齐人听说田儋战死，就拥立田假为齐王，田角为相国，田间为大将，以对抗诸侯。
七月，大雨连绵，刘邦和项梁联合北上营救，在东阿大破章邯，救回田荣。随后，刘邦又与项羽继续北追章邯至城阳，屠了此城。刘、项大军驻军濮阳东，再次击败章邯。章邯重整旗鼓后，在濮阳周边挖掘护城河，加强守备。于是刘、项调转兵锋进攻定陶。
八月，田荣驱逐田假，立田儋之子田巿（fú）为齐王，自己担任相国。田假逃往楚，田角、田间逃往赵。刘邦、项梁未能拿下定陶，于是转而向西进攻至雍丘，大败秦军，三川郡守—李斯之子李由被项羽所杀。随后回兵攻打外黄，但未能取胜。
项梁屡破秦军后，面露骄色，宋义劝他低调点，但项梁听不进去。后来宋义对齐国使者说，项梁如此则必败。章邯虽然屡败，但作为几乎唯一一个能够抵抗叛军的秦将，还是获得了秦朝的增兵。
九月，章邯静默行军，夜袭定陶，大破项军并杀了项梁。这就是所谓的“骄兵必败”，班固在《汉书·魏相传》中正式写出“兵骄者灭”，这也是该成语的出处。此役，项梁曾向田荣求援，但田荣要求楚国和赵国分别先杀掉田假、田角和田间，被楚怀王和赵国拒绝。齐国最终没有出兵，田荣和项羽由此积怨。
刘、项大军正在攻打陈留，听闻项梁战死，军心大动，于是与将军吕臣向东撤兵，将义帝从盱台迁往彭城。吕臣驻兵彭城东，项羽驻兵彭城西，刘邦镇守砀县，呈拱卫彭城之势。
闰九月，齐国使者向怀王报告了宋义对项梁兵败的预言，怀王召见宋义，相谈甚欢，于是任命他为上将军，号子卿冠军。同时，还将吕臣、项羽的军队合并，亲自率领，命刘邦为砀县郡守，封武安侯，率领砀县军队；命项羽为鲁公，封长安侯。诸将均听令于宋义。
《汉书》并未解释怀王为何在此时分封刘邦和项羽。根据当时的局势推测，这可能是怀王趁项梁去世之机，暗藏私心的一次权力重新分配。怀王当初被项梁拥立，虽然从庶民一跃成为天下共主，但也清楚自己只是个傀儡。如今项梁战死，他有机会摆脱束缚谋求掌权了，但项羽并非等闲之辈，因此他才决定亲帅项军，并给刘邦也封个侯位，以此来制衡项羽。
所以，从某种程度上讲，刘邦地位的提升，是怀王与项羽两股力量博弈的产物。这可能也是刘邦作为天选之子的运气，后面刘邦在创业之路上还会遇到几次这样的运气。不管怎么说，刘邦此次封侯奠定了自己为一方诸侯的地位，拥有了共分天下的资格。
斩杀项梁之后，章邯便认为叛乱的楚兵已不足为虑，于是北渡黄河攻击赵王黄歇，并取得了大胜。黄歇退守巨鹿城，秦将王离将兵围城。
起兵初期，怀王与各路将领有约在先：“先入关中者，封关中王。”怀王为什么要许诺如此肥沃的地盘呢，因为当时秦强楚弱，众将都不想消耗自己先打关中。唯有项羽想要替叔父项梁报仇，怒火中烧，想要同刘邦一起西入函谷关。看来这个时候，两人关系还不错。
但怀王手下众老将都说：“项羽为人残暴，经常屠城。而且前面陈王、项梁均获败绩，何不派遣一位长者仗义西去，以求安抚秦地父老。秦地父老苦秦久矣，如今若派出一位长者，宽厚待民，则更容易取胜。项羽显然不合适，而沛公向来宽厚仁义，非常合适。”最终，怀王决定派刘邦攻打关中，并收编陈王、项梁剩下的散兵。刘邦奉命领兵从砀县出发，向咸阳进发。而项羽则被怀王任命宋义的副将，领兵北上救赵，范增为末将。
秦二世三年十月，齐将田都背叛齐王田荣，领兵帮助项羽北上救赵。
此时项羽与宋义的军事思想发生了矛盾。面对赵国被围的局势，项羽主张带兵渡河北上，与赵军内外呼应，一举破秦。而宋义则认为，楚军可作壁上观，让秦、赵相互消耗，不论什么结果，都有利于楚。宋义还对项羽说：“披坚执锐我不如你，而运筹帷幄你不如我。”在此期间，宋义还为儿子设宴践行。
项羽十分反对宋义的思想，又逢天寒大雨，士兵忍饥受寒，宋义不但不抚恤士兵，反而沈溺酒宴。于是项羽便在某天早上将宋义斩杀于军帐中，对外宣称宋义勾结齐国谋反，自己是执行楚怀王秘令将其诛杀，并派人追至齐国杀了宋义之子。诸将莫敢不从，共同推举项羽为代理上将军。项羽派楚桓将这些情况报告给怀王，此时怀王又能有什么办法呢，只能默认，于是项羽正式成为上将军。
杀了宋义后，项羽威震楚国。十二月，已故齐王田建之孙田安带兵加入项羽军队，北上救赵。楚军以一敌十，声动天地，联军在项羽的带领下大败秦军于巨鹿，秦将王离被俘，章邯遁逃。战胜秦军后，曾经佯装救赵实则作壁上观的诸侯们只敢跪行来拜见项羽，项羽自此真正成为了诸侯领袖，结束了各路起义队伍群龙无首的状态。
此时刘邦正在南线作战，逐步向咸阳推进。十二月，刘邦带兵至栗县，遇到刚武侯，夺取其兵马四千人，与魏国将领皇欣、武满合兵大败秦军。二月，刘邦从砀县向北进攻昌邑，遇到了彭越，但在其帮助下也未能攻克昌邑。
刘邦继续西进，路过高阳时，门卒郦食其求见刘邦，说他是路过这里的众多将领中最为气度不凡的。此时刘邦正在彰显本色：坐在床上，命两名女子为自己洗脚。郦食其见此情景，不拜，仅双手作揖，说道：足下要想诛灭暴秦，就不该坐着接见长者。刘邦最大的优点就是听人劝，于是立刻起来整理衣冠，引入上座。郦食其建议刘邦攻打陈留，刘邦任其为广野君，令其弟郦商将兵攻打陈留。郦商从陈胜起兵时就开始聚集少年，此时已有四千之众。
三月，刘邦攻打开封未果，领兵向西又与秦将杨雄战于白马，随后又在曲遇东与其交战，取得大胜。杨雄败走荥阳，秦二世遣使将其斩首示众。
四月，刘邦向南攻打颍川并屠城。因为张家世代为韩国国相，故又倚靠张良的攻下了韩国十多座城池。刘邦令韩王成留守阳翟，自己与张良继续南下进攻宛县，然后计划取武关进入咸阳。
刘邦起兵至今，已经屠过了成阳（与项羽一起）和颍川，所以刘邦并非真正的宽厚长者，而项羽也并非所谓残暴之人。《史记·陈丞相世家》记载“项王为人，恭敬爱人”，《史记·淮阴侯列传》记载“项王见人，恭敬慈爱，言语呕呕。人有疾病，涕泣分食饮”。吕思勉先生认为，对项羽残暴的评价来自于他坑杀俘虏，而这是“兵权不得不然”，入关、破齐之后的行为，是因为当时的士兵多为“僄（biāo）悍无赖之徒”，很难约束，故而为之，当时也并非只有项羽这么做。
所以，怀王选择刘邦攻打关中，宽厚只是一个说辞，实则忌惮项羽的实力。因为若命项羽攻打关中，以楚军的以一敌十和项羽的国恨家仇，则关中必克。若如此，项羽极有可能依仗关中的地盘和财富，称王天下，到那个时候怀王还有什么生存空间呢？所以怀王派宋义带领项羽北上与秦军相互消耗，而相对弱小的刘邦成为了进攻咸阳的人选。