秦始皇二十四年（前223年），秦灭楚，沿袭楚旧郡设立泗水郡。青年刘邦现年只是一介布衣，曾经到秦朝首都咸阳参加徭役，其间任意观览，望见了秦始皇，非常地感叹说：“哎呀，大丈夫就应当像这样啊！通过考核成为秦朝官吏，做了泗水的亭长（刘邦的亭长，大概相当于现代的一个村长兼派出所所长，亭，和郡一样，最初不是管民的，而是军事单位，但它更像哨所，并不用于屯兵，所以亭没能和郡一样发展起来，逐渐成为无秩官员，也就是国家编制外的，虽说秦朝统一了，但亭一级的官员并没有裁撤，也没有录入秦朝的编制官吏）。

在任上，刘邦戏弄县廷官吏，又喜欢喝酒，爱好美色。一次，刘邦以亭长的身份为泗水郡押送徒役去骊山，徒役们有很多在半路逃走了。刘邦估计等到了骊山也就会都逃光了，所以走到丰邑西边的水泽地时，就停下来饮酒，趁着夜晚把所有的役徒都解绑释放了。刘邦说：“你们都逃命去吧，从此我也要远远地走了！”徒役中有十多个壮士愿意跟随他一块走。最后，刘邦带着这些人逃匿在芒县、砀县的山泽（今通称芒砀山）之中。在此期间，发生了所谓刘邦夜醉斩蛇、“赤帝子”、吕雉宣称刘邦有“云气”等奇事，沛县之中的年轻子弟听说后，很多人都要前去投奔他。随后，刘邦的队伍不断扩大，有数百人之众。

由于秦朝连年发起大型徭役，以各地男丁往北修长城戍边；以童男童女和百工几千人出东海求仙；征集无夫家的女性一万五千人南下百越，最终导致中原疲敝，百姓乱离，人们私底下都想要反抗暴秦，当时“欲为乱者十家而七”。（秦二世元年，前209年），陈胜、吴广聚众起义，陈胜在陈县自立为王建立了“张楚”（大张楚国），和秦朝分庭抗礼。

陈胜起义后，当时，沛县县令也想响应反秦起义，萧何和沛县狱掾曹参劝县令将本县流亡在外的人召集回来，一来可以增加力量，二来也可以杜绝后患。县令觉得有理，便让樊哙去邀请刘邦，刘邦当时已坐拥兵力数百之众。然而不久沛令又后悔了，害怕刘邦回来反而引发变乱。所以，他命令关闭城门来坚守，并准备杀掉萧何和曹参。萧曹二人闻讯赶忙逃到城外投奔刘邦。刘邦将一封帛书射进城中，号召城内百姓杀掉县令以响应诸侯反秦。沛县父老于是组织子弟杀死县令，开城门迎进刘邦。萧何、曹参都是文吏，担心身家性命，深恐举事不成，被秦朝诛灭九族，就竭力推举刘邦来领导大家起事。大家推举刘邦为沛县县令，依楚制称作沛公。刘邦便顺应天意，设祭坛，立赤旗，因早前的赤帝子的传闻，所以崇尚红色，很快义军扩充到三千人。

刘邦集合三千子弟在沛县响应反秦义军，先是率军攻打胡陵县、方与县，秦国泗水郡的郡监平率兵包围丰邑，众人回守丰邑，两天后，刘邦出兵应战，击破秦军。于是泗水卒史周苛、周昌兄弟归顺刘邦阵营。接着令雍齿守丰，自己率领军队进入薛县，与秦军大战。泗水郡守壮战败，逃至戚县，刘邦麾下的左司马追斩壮。刘邦所部再次进攻胡陵县，夏侯婴与萧何前去劝降镇守胡陵城的泗水郡监平，平于是举城投降。接着刘邦率军返回亢父县、方与县，命曹参镇守方与县城。这时魏相周巿来攻方与，方与城转投魏国，曹参率军迎击。雍齿据守的丰邑也被周巿招降，刘邦大怒，举兵攻丰，没有攻克。恰在此时，刘邦又患病，只得还军沛县。

这时，刘邦听说东阳甯君与秦嘉立景驹为楚王，驻扎在留县（今沛县东南），于是投奔景驹，欲借军攻丰邑。在去投奔景驹的路上，遇见了也要投奔景驹的张良。两人于是兵合一处。张良与刘邦二人一见交谈之后，大有相见恨晚之意。于是张良放弃投奔景驹的念头，直接投奔到刘邦这边。刘邦授张良为厩将。然后一起去向景驹请援。这时秦大将章邯的部将司马夷攻略楚地，屠戮相县（今安徽淮北市），到达砀县（今永城芒山镇）。于是刘邦与东阳甯君率军向西，迎击司马夷，在萧县西与秦军展开战斗，结果不利，刘邦与东阳甯君退至留县。补充军队和粮草后，再次进攻秦军，以少胜多三天攻下砀县，收降砀县军卒六千人，加上原有部队总计九千人。

三月，刘邦攻取了下邑（今安徽砀山），返回再次攻丰，结果仍然没攻下。之前，原楚国贵族的后代项梁、项羽在吴县（今江苏苏州）起兵，后渡过淮河扩张势力，攻灭秦嘉、景驹等部。刘邦听说项梁在薛县，于是留下军队包围丰邑，自己率领一百余骑至薛县见项梁。项梁给刘邦增兵五千、五大夫将十人，三攻丰邑。雍齿不敌，逃奔魏国。

刘邦举部投奔反秦义军首领项梁，刘邦从属项梁一个多月后，项羽也攻下襄邑也还至薛县。当陈胜死亡的消息被证实，项梁把别将全都召回薛县，采纳范增的建议，拥立战国时楚怀王熊槐的孙子熊心为楚王，仍号称楚怀王，定都盱眙。刘邦与英布、蒲将军、吕臣、陈婴等别部将领共同参与拥立了楚怀王熊心。（楚怀王这个称号本是战国时期楚国国君熊槐的谥号（死后才有的），在熊心被拥立的时候被用来作为熊心的王爵爵号。《史记·项羽本纪》记载：“于是项梁然其言，乃求楚怀王孙（熊）心（于）民间，为人牧羊，立以为楚怀王，从民所望也。”这，就是熊心生前就被称为楚怀王的原因。）

拥立楚怀王后，项梁率军北上救援齐魏，在亢父、东阿等地大破秦军。这时齐军因内部矛盾而撤还，只有楚军追击秦军。在这期间，刘邦率领曹参、周勃等人与章邯的车骑部队交战，将其击退，平复蒙邑、虞县、爰戚县、东缗县、栗县、啮桑县、宛朐县、单父县等大量秦军占领的魏国城池，史称“定魏地”。项梁下令楚军分军，以刘邦、项羽领兵，率楚军一部攻城阳。刘项二人率军攻下城阳（即成阳，今山东菏泽市东），屠之。然后追击秦军至濮阳东，再次大破秦军。秦军这时得到增援，军势再次振兴，据守濮阳，放水环绕城池。刘项二人于是绕过濮阳，转攻定陶（今山东定陶）。定陶未攻下后，又向西攻打雍丘（今河南杞县）。刘项两军大破秦兵，刘邦麾下曹参斩杀三川郡的郡守李由，并俘虏秦侯一人。

正当刘项两军进攻陈留之时。章邯大破项梁于定陶，项梁战死。刘项二人大惊，在商量后决定放弃陈留，还军东归。刘项二人分兵，项羽军驻彭城西、吕臣军驻彭城东，而刘邦军驻砀县。项梁之死，使诸侯震怖。而秦军更是挟战胜余威常追亡逐北。章邯经过连番胜利，认为楚国已不足虑，于是北上进攻赵国，攻下邯郸后把民众都迁徙到河内，并毁掉邯郸的城墙。而赵军退守巨鹿，章邯率军进围赵王歇与赵相张耳于巨鹿。

项梁死后，楚怀王把都城由盱眙迁至彭城，将吕臣与项羽的军队合并起来自己统领。封刘邦为武安侯，升任砀郡长（郡守），统率砀郡兵马；项羽为长安侯，任鲁公。过一番调整之后，楚国局势稳定下来。刘邦此时已统筹整个砀郡旧魏地区兵力。与此同时，被困于巨鹿的赵王歇与张耳遣使至楚向楚国求救。楚怀王答应救赵。但为了分散秦军力量，决定派一支部队西向直接攻秦。楚国北路军以宋义为主将，西路军以刘邦为主将。约定谁先入关中，谁就可在关中称王。（先入关中者为王成语典故出处）

当时由于陈胜、项梁相继败亡，秦军兵势正盛，楚国上下皆不看好西征，谁都不愿意领军西征。怀王身边的老将们认为唯独刘邦向来宽厚，是有德行的长者，适合“扶义而西”，减少西进阻力，能更好地不动用暴力让秦国父老归顺，于是任命刘邦为西征军统帅。而项羽则因为叔父之死，比较激愤，积极要求随同刘邦西征。但所有老将皆以项羽为人“僄悍滑贼”及“所过皆残灭”不利于西征为由拒绝了项羽的要求，让他担任北路军的次将北上救赵。

秦二世3年10月（前208年11月25日至12月23日期间），刘邦军往西攻城略地，一路收集陈胜、项梁的散卒。经由砀县到达成阳县，先在成武县南面攻破东郡的郡尉所率领的部队，又在成阳县南面攻打王离军，在杠里与秦军对垒相持，攻破秦二军、河间守军，刘邦率领曹参、樊哙、灌婴、傅宽、郭蒙等与秦将王离交战，大破其军。接着，刘邦引兵西进，在昌邑（今山东巨野东南）遇到彭越的部队，遂与其合力进攻昌邑，没能攻下，只得返回栗县（今河南夏邑）。在栗县时，刘邦遇到刚武侯，并且吞并他的部队，刘邦的军队增加了四千多人。接着与魏将皇欣、魏申徒武蒲军合攻昌邑，又没攻下。刘邦决定舍弃昌邑不打，率军西行。

二月，刘邦西经高阳县，郦食其是高阳里的门卒，认为经过高阳的军队很多，只有刘邦拥有很大的器量，于是求见刘邦。此时刘邦坐在床上。令两个女子替他洗脚。郦食其未行拜见之礼，拱手长揖说：“足下要是真想推翻无道之秦，就不应坐着来接见长者。”刘邦听后而起，整衣表示歉意，请入上座。郦食其建议刘邦袭击陈留。刘邦采纳郦食其的计策，袭击陈留县，得到秦军囤积的粮草。刘邦封郦食其为广野君，任命他弟弟郦商为将，领陈留之军。刘邦军在亳县南部与秦军交战，又往西到达开封，秦将赵贲率领秦军在开封北面与刘邦交战，刘邦携麾下曹参、樊哙、夏侯婴、灌婴、傅宽、靳歙等大败赵贲。赵贲兵败退守开封城，郦商率领陈留县兵，与刘邦、曹参一同包围开封城，没有攻下。刘邦转而西进，率领麾下曹参、樊哙、夏侯婴、傅宽、郭蒙等人在白马、曲遇东面与秦将杨熊交战，大破杨熊军，曹参俘虏秦国司马、御史各一人；夏侯婴累计俘虏六十八人，收降士卒八百五十人，并缴获官印一匣。刘邦部队又在阳武再次击退杨熊。杨熊败走逃至荥阳，被秦二世派人杀死。