因为农民起义四起，各地郡县的郡守、县令纷纷被杀。九月，沛县的县令觉得形势不妙，十分惶恐不安，只好准备在沛县响应陈胜起义，以稳定民心，保住自己的小命。为此，沛县的献陵和在府衙当值的主吏萧何、曹参一起商量起兵反秦的事宜，萧、曹对沛令说：“您现在依旧是秦朝的官吏，今天背叛了朝廷，准备率领沛县的子弟进行起兵，沛县的子弟恐怕一时半会儿并不能听从您的命令。如果您能把逃亡在外的人都召集过来，到时能够得到数百人，然后在利用这些人来控制民众，就不怕民众不听从您的命令了。”
沛令一听便知道萧、曹所说的“逃亡在外的人”指的是匿身于芒山、砀山的刘邦，这几乎是沛县无人不晓的事。于是沛令命沛县以屠狗为业的樊哙前往山中召回刘邦。
樊哙到达山中，见到刘邦，向刘邦转达了县令的意图，同时也向刘邦捎去了萧何、曹参的口信。这时刘邦在芒砀山所聚集的徒众已有数十百人。刘邦在山中早已闻知陈胜大泽乡起义，天下响应，心想自己也不能久居山中，正待机而起。今见樊哙带来沛令和萧曹的旨意，十分高兴，当即率徒众离开山林，与樊哙一同启程。
刘邦尚未到达沛县县城时，沛令有些后悔。他不仅知道刘邦与萧、曹有着特殊密切的关系，也深为各地豪杰杀死郡守、县令而后起义的无数事实所震恐，担心刘邦入城后会发生变故，与萧曹合谋杀死自己，然后再举行起义。于是，当刘邦率徒众来到沛县城下时，沛令紧闭城门防守，不予接纳入城；同时，想诛杀萧何、曹参，萧、曹恐惧，越城投奔刘邦，以求受到保护。刘邦在绸绢上写信，捆绑在箭杆上射入城中，向城中父老说：“天下人受暴秦的苦难已是很久了，今日父老虽为沛令守城，但天下诸侯并起反秦，沛城即将遭到屠杀。如果大家起来共同诛杀沛令，推选出一位首领带头响应诸侯，你们的家室都可以得到保全。不然的话，父子都将遭到屠杀，那就太不值得了。”
于是，城中的父老率领子弟共同杀死沛令，开城门迎接刘邦入城。刘邦入城后，城中父老想要推举他为沛令，刘邦辞谢说：
“当今天下大乱，各路诸侯并起反秦，如果选择将领不当，将会一败涂地。我不是爱惜自己的性命，只是担心自己的才能薄弱，不能保全沛县的父老兄弟。这等大事，愿大家推举可以胜任的人。”
当时在场的萧何、曹参都是文官，爱惜自身，顾虑多端，担心大事不成后被秦朝诛灭全家；同时，萧、曹又深知刘邦能成就大事，便都推举刘邦。诸位父老们对刘邦说：“我们早就听说过有关您的种种奇闻，日后定当显贵；况且我们已经占卜过了，没有人比您更为吉利的。”
刘邦还是多次推让，但众人谁也不敢领头起义，最终还是推举刘邦做了沛公。
刘邦自第一次入关中，在咸阳纵观秦始皇帝车驾出游之后，便做起了皇帝梦。沛县父老推戴他为沛公，他喜在内心，但表面上却再三推让。刘邦深知在场的人谁也不敢为首领，他的推让再三，是为着表明他带头起义不是出于私心，不是为了封侯称王，而是在父老子弟们的再三推举之下，不得已而为之，目的是救民于水火；同时也是为着起义后有效地管束部下：既然是众人推举，众人就应当服从管束和指挥。
刘邦与各路起义军首领的不同之处在于，他起义时不是为着封侯称王，而是把起义的第一天，视为踏上夺取皇帝宝座征程的起点。因而，当他答应沛县父老做沛公时，便胸有成竹地把起义的仪式举办得颇为望而庄严，与众不同。
在沛县县府的大庭之中，刘邦带领父老子弟们祭祀黄帝与蚩尤，这是因为黄帝传说中上古的五帝之首，是中原各族的共同祖先，又善于战略战术；而蚩尤作为南方部族的首领，首创各种兵器，又英勇善战。可见，刘邦起义前祭祀黄帝与蚩尤，为的是求得神灵的保佑，保佑起义后战无不胜，攻无不取，最终即皇帝之位。祭祀后，又用牲畜的血涂在战旗和战鼓之上，祭了战旗和战鼓。为取代秦皇帝，刘邦令起义军的军旗一律为红色。于是，萧何、曹参、樊哙在沛县四出召收弟子，共得3000人，进攻胡陵（今山东鱼台县东南）、方与（今山东鱼台县西北），还守丰邑（今江苏丰县）。沛公所率领的这支起义队伍，从此加入了秦末农民大起义的洪流之中。
刘邦于秦二世元年（公元前209年）九月于沛县举兵起义，转眼间已是十月。秦以十月为岁首，已是秦二世二年，当时天下的形势是：周文所统率的十万义军在戏水被章邯所统率的秦军打得大败而退还，继武臣自立为赵王以后，他派往燕地的韩广在燕地自立为燕王，狄人田儋在齐地自立为齐王，宁陵君魏公子魏咎被陈王立为魏王，项梁及项籍起兵于吴后，渡江加入反秦行列。
陈王陈胜、赵王武臣、燕王韩广、齐王田儋、魏王魏咎以及项梁与项籍，是秦二世二年年初反秦各路诸侯中的几支主要力量，无不拥有一定的实力。而起兵于沛县的沛公刘邦，此时人少力单，处于举步维艰的境地。
刘邦退守丰邑后，当时章邯率秦军东下，秦泗水郡（治所在相县，今安徽淮北市西北）名叫平的郡监率兵围攻丰邑。沛公领兵出战，击破秦军，命同乡雍齿守卫丰邑，自己领兵进攻薛（今山东滕县南）。泗水郡郡守名壮，在薛县战败，逃至戚县（今山东滕县）。沛公的左司马曹无伤捉住壮，并将他杀死。沛公领兵回到亢父（今山东济宁市南），到达方与，一路没有与敌军交战。此时，陈王派魏入周襳东向攻城略地，周襳派人对雍齿说：“丰曾是魏国的大梁秦军攻占后的迁都之地，今魏王已平定数十城，您如果以丰邑投降魏国，魏国封你为侯，令你守卫丰城；如不投降，将屠杀丰城。”雍齿本来不愿归属刘邦，在周襳利诱威胁之下，便反而为魏国守卫丰城。
沛公得知雍齿反叛，带兵围攻丰，未能攻下。由于患病，刘邦便回到沛县。雍齿以丰邑背叛沛公，在精神上给沛公的打击很大，他十分怨恨雍齿及丰邑子弟在形势不利情况下的背叛行为。当时，章邯所率领的秦军气势正盛，陈王陈胜被叛徒庄贾杀害，起义军一时群龙无首，宁陵君与凌县（今江苏泗阳县西北）人秦嘉合谋立楚国的王族后裔秦嘉为“假王”，驻扎在留（今江苏沛县东南）。沛公前往归附景驹，想要向景驹借兵攻打丰邑。但秦将章邯、偏将司马尼所率领的秦军由西向东追击，平定楚地，在相县（泗水郡治所）屠城之后，到达砀（今河南夏邑县东南）。东阳宁君、沛公率军西上，与司马尼交战于萧（今安徽萧县西北）西，不利，退回留县，收编人马，率兵攻砀。围攻3日，砀城被攻下，收编砀城人马，得五六千人。又进攻下邑（今安徽砀山县），将下邑攻克，然后回军丰县。这时，沛公闻听项梁在薛县，便带领百余名骑兵前往拜见，项梁拨给他步兵5000人，五大夫将10人。沛公带兵回还，攻打丰邑。
沛公投奔项粱一月有余，项羽已攻克囊城（今河南襄城县西）而还。项梁闻知陈胜已死，立楚怀王的孙子熊心为楚王，都于盱台（今江苏盱台县东北），项梁号武信君。项梁攻派沛公、项羽攻打城阳（今山东鄄城县东南），攻克后屠城，驻军于濮阳（今河南濮阳县西南）东，与秦军交战，大破秦军。战，大破泰军。
秦军重新振作，坚守濮阳并引水环城以自卫。楚军离去而进攻定陶（今山东定陶县西北），未能攻下。沛公与项羽向西攻占土地，到达雍丘（今河南圮县）城下，与秦军交战，犬破秦荤，三川郡郡守、秦丞相长子李由被斩首。沛公与项羽回兵攻打外黄（今河南民权县西北），未能攻下。
项梁因屡败秦军，面有骄色，不听从上将军宋义的劝谏，在定陶被章邯所带领的秦军打得大败，项梁战死。正在进攻陈留（今河南开封县东南陈留城）的沛公、项羽闻知项梁战死，与陈胜的部将吕臣一道率兵回师东进。吕臣驻军在彭城（今江苏徐州市）东面，项羽驻军在彭城西面，沛公驻军于砀山-一带。
项梁的军队被秦朝的将领章邯攻破之后，章邯认为楚地已经不足为虑，于是就渡过黄河上北面准备镇压河北地区的各路起义军。项梁在秦二世二年九月的时候战死。因为项梁的兵败战死，楚怀王感到十分恐惧不安，于是把都城迁到了彭城，并把吕臣和项羽的军队进行了合并，都交由自己率领。把刘邦任命为砀郡长，封为武安侯，率领砀郡兵马；把项羽封为长安侯，号为鲁公；将吕臣任命为司徒，并将其父亲吕青任命为令尹。
