秦二世元年(前 209 ) 秋七月， 陈涉在蕲县起义，到陈地，自称为楚王。派武臣、 张耳、 陈余略取赵地。八月，武臣自立为赵王。各郡县相继发生杀死主要官吏以响应陈涉的事。九月， 沛县令想用沛县响应陈涉，幕僚萧何、 曹参进言说：“你身为秦朝官吏，现在想背叛秦朝， 想率领沛中子弟起义，大家恐怕不会相信。望你招收那些逃亡在外的人， 可以得数百人，靠这些人的力量来号召有顾虑的沛中子弟， 沛中子弟就不能不听。” 于是沛县令派樊哙去邀请高祖。此时高祖已经拥有数百之众了。
当樊哙与高祖率众前来时，沛令反悔了，害怕高祖夺取他的权力，就闭城固守，还想诛杀萧何、 曹参。萧、 曹甚为惊恐，就偷越城墙去投靠高祖。高祖即写帛书射到城上。书上告沛县父老说： “普天之下都痛恨暴秦。今日各位父老虽为沛令守城，而各地义军一到，就会在沛地大动刀兵。要是各位能在现在诛杀沛令，推举众望所归的人为首领，以响应起义，就可以保证家室安全。否则，全家都要遭殃，这是毫无代价的。” 于是沛中父老率其子弟杀死沛令， 大开城门迎接高祖，要推举高祖做沛县令。高祖辞道：“当今正值天下大乱，群雄纷纷起义， 要是选拔首领不当，就会一败涂地。我并非贪生怕死，而深恐力不胜任，不能实现各位父老的重托。这是一件大事，请求再选择一位能人。 ” 萧何、 曹参都是文吏，担心其身家性命，深恐举事不成，被秦朝诛灭九族， 就竭力推举高祖。沛县父老都说： “平日常闻刘季一些奇异之事， 有可能成为贵人，我们曾问卜于神明，刘季是最佳人选。 ” 高祖多次辞让， 大家都不同意，高祖于是立为沛公。对古天子黄帝、 蚩尤在沛廷进行祠祭。并用牲血祭旗鼓。旗帜俱为赤红色，这是由于所杀之蛇是 “白帝子” ，而挥剑斩蛇者是 “赤帝子” 的原因。于是青年豪吏如萧何、 曹参、 樊哙等都招募沛县子弟，使义军扩充到三千人。
同月，项梁与兄子项羽起义兵于吴。田儋与堂弟田荣、 田横起兵于齐，自立为齐王。韩广自立为燕王。魏咎自立为魏王。陈涉的大将周章西入函谷关，兵至戏水，秦将章邯迎敌打败了周章。秦二世二年十月，沛公攻打胡陵、 方舆后，回师丰邑。秦泗川监平领兵围丰。二月，沛公发兵与战，打败秦军，派雍齿守丰。十一月，沛公领兵到薛。秦泗川守壮的兵被击败，壮逃到戚，被沛公的左司马得杀死。沛公兵还亢父， 到方舆。赵王武臣被部将所杀。十二月，楚王陈涉被其御手庄贾所杀。魏将周市略取丰沛，派人对雍齿说： “丰曾是魏的临时都城，今日魏地已被收复数十城。雍将军如能归顺于魏，魏就委你为侯镇守丰地；若不归顺， 魏兵就要屠城。 ” 雍齿平素本不愿居沛公之下，到魏招降时，就归顺于魏而为魏守丰了。沛公攻丰，无法攻下。沛公引兵回沛，对雍齿与丰子弟的叛变恨恨不已。
秦二世三年正月，张耳等立赵国之后赵歇为赵王。东阳甯君、 秦嘉立景驹为楚王，驻留县， 沛公投奔景驹，路遇张良，就一道晋见景驹，请景驹派兵攻丰。此时陈涉的将军司马夷领兵北定楚地，血洗相县， 兵至砀县。东阳甯君与沛公引兵向西，与司马夷战于肃县之西，不能取胜，收兵回留训练。二月，攻打砀县，三日攻破砀城，收编守砀的部队，得六千人。与原来的三千人会合共九千人。三月，攻下邑县， 得胜。回师攻丰， 未胜。四月，项梁击杀景驹、 秦嘉，驻兵于薛，沛公到薛晋见项梁，项梁为沛公增兵五千、五大夫将十员。沛公回原地后，领兵攻丰，收复了丰县。雍齿逃到魏地去了。五月，项羽攻下襄城后返回。项梁把在别处的小将全部召回。
六月，沛公到达薛地，和项梁共立楚怀王孙芈心为楚怀王。秦将章邯破杀魏王咎、 齐王田儋于临济。七月， 连天阴雨。沛公攻打亢父。章邯围齐将田荣于东阿县，沛公与项梁一同领兵救田荣，在东阿大败秦将章邯。田荣领兵回，沛公、项羽追赶秦兵，到城阳县，血洗城阳， 驻军于濮阳东，再次与章邯开战，又一次打败秦兵。
章邯重振旗鼓，守卫濮阳，掘壕引水自固。沛公、 项羽就移兵另攻定陶。八月，田荣立田儋子田市为齐王。定陶未攻下，沛公与项羽收取土地至雍丘，与秦兵战，大败秦兵，斩杀三川太守李由。回师攻外黄，未能攻下。
项梁再次打败秦军， 就面露骄色。宋义提醒他应提高警惕，项梁毫不在意。九月，章邯在黑夜中人衔枚、 马疾走， 袭击驻兵定陶的项梁，大破无备的项梁之军，杀死项梁。当时阴雨连绵从七月到九月。沛公、 项羽攻打陈留，听到项梁死讯，士卒惊恐， 于是与将军吕臣引兵向东，将楚怀王由盱眙迁都到彭城。吕臣驻兵于彭城之东，项羽驻兵于彭城之西，沛公驻兵于砀。魏咎之弟魏豹自立为魏王。闰九月，怀王合吕臣、 项羽所领之军归自己直接指挥，派沛公为砀郡长，加封武安侯，领砀郡之兵。任项羽为鲁公，加封长安侯，任吕臣为司徒，吕臣的父亲吕青为令尹。
秦将章邯在打败项梁之后，认为楚地的叛秦势力已不足为患，就渡河北上攻打赵王歇， 大败赵王歇。赵王歇退保钜鹿城，秦将王离兵围钜鹿。赵王多次求救于楚怀王，怀王就任宋义为上将，项羽为副将，范增为末将。领兵北救赵军。原先，怀王曾与诸将相约，谁能先平定关中就封之为王。这时期，秦兵强大，常常乘胜追击义军，诸将都畏其威而不敢入关。独有项羽恨秦军打败并杀死项梁，十分愤激，愿意和沛公西进入关。怀王的一些老将都说： “项羽为人？悍好杀，原先攻下襄城，襄城几无遗类，项羽所过之处都遭残灭。且楚军在多次进取中前楚王陈涉、 项梁都以失败告终，不如另派一位宽厚长者仗义西进， 告谕秦地父老兄弟。秦地人民受秦朝之苦已久，要是果真有一位长者领兵，秋毫不犯，秦都咸阳应当是能够攻下的。项羽不能担此任，只有沛公平日就是一个宽大仁厚的人。 ” 最后怀王不同意项羽西进，而派沛公西收陈涉与项梁的散兵。于是沛公从砀地出发，到城阳与杠里，攻打秦军防地，打败了两地守军。秦二世三年十月，齐将田都叛变齐王田荣，田都领兵帮助项羽救赵。沛公在成武打败了秦东郡尉的部队。十一月，项羽杀掉了上将宋义，兼并了宋义之军后渡过黄河，自封为上将军。宋义原有将领如英布等都归辖于项羽。十二月，沛公引兵到达栗县，遇见楚怀王将军刚武侯，也夺取了他所率的四千部队，并成一军和魏将皇欣、 武满的军队会合，进攻秦军，大败秦军。前齐王田建之孙田安领兵由济北跟随项羽救赵。项羽大破秦军于钜鹿，俘虏了秦将王离，秦将章邯逃走。