蕭何從呂雉處到知劉邦的下落後，雖然心中為好友擔心，但因為劉邦犯下的是死罪，他也無能為力，隻得默默等待參幫助劉邦脫困的機會。不久，機會就來了，陳勝、吳廣的起義，不僅改變了劉邦的命運，也讓蕭何走上了起兵造反的道路。
秦二世元年（前209年）七月，即秦始皇死去一周年之際，朝廷下令征發居於閭左的平民百姓，罰至漁陽（今北京市密雲縣西南）戍守邊境。這時，有一支900餘人的守邊隊伍在北上途中駐紮在大澤鄉（今安徽省宿縣東南劉村集），陽城（今河南登封縣東南告成鎮）人陳勝和陽夏（今河南太康縣）人吳廣也被編入這支被罰守邊的隊伍之中，並被指派為“屯長”（小隊長）。
陳勝字涉，青年時因家貧受雇為他人耕種田地。一日，他與同受雇傭的夥伴們耕田，在田埂上休息時，他麵帶怨恨不平的神色凝視遠方，久而無語。正當夥伴們要向他詢問何故如此時，他卻回首激動地說：“今後若是有人富貴了，彼此都不要忘了誰。”
“你現在是受雇為別人耕田，有什麼富貴可言？”夥伴們笑著回答說。
陳勝見夥伴們嘲笑他，很不服氣，激動地說：“燕子、麻雀怎會知道大雁、天鵝的誌向！”
就是這位青年時代便胸懷大誌的人，如今也未能逃出被罰戍邊的命運。在大澤鄉，又趕上天降大雨，道路不通。望著滿天烏雲，陳勝估計無論如何也難以在規定日期內到達漁陽。按秦二世更定的法律，戍卒守邊誤期，無論有任何理由，都要依法一律斬首。在即將降臨的死亡麵前，陳勝與吳廣謀劃道：
“大雨不止，道路不通，我們已無法按期到達，依法都要問斬。如今的形勢是，到達漁陽後必死無疑。逃亡是死罪，起義幹一番大事業也是死罪，同是一死，那麼為國而死好嗎？”
陳勝說：“天下百姓苦於秦的暴政，已是很久了。我聽說二世是始皇帝的小兒子，不當立為皇帝；應當立為皇帝的是公子扶蘇。扶蘇因多次勸諫始皇帝，被派到外地去統兵。現在聽人說扶蘇無罪，卻被二世殺害。百姓們都說扶蘇賢能，還不知道他已經死去。項燕是楚國的名將，屢立戰功，愛惜士卒，楚國人都很愛戴他。有人以為他死了，有人以為他逃亡在外。現在以我們這些人冒稱是公子扶蘇、項燕，為天下人帶頭起義，一定會有很多人響應。”
吳廣認為陳勝講得很對，便按照當時的習俗去向算卦先生占卜吉凶。算卦先生明白他們的意圖，開口說道：“你們的事都成，能立大功，然而你們還是應當向鬼神問卜啊！”
陳勝、吳廣聽算卦先生這麼一講，很高興，想到了鬼神，說：
“這是教我們先借鬼神在眾人中取得威望。”
於是，吳廣暗中用朱砂在帛上寫了“陳勝王”三字，清晨偷偷地塞入剛剛捕撈的鮮魚腹中。戍卒早上到市上買魚，烹食前發現魚肚中的帛書，上麵寫有“陳勝王”三字，感到很奇怪。夜晚，陳勝私下派吳廣到駐地附近樹叢的神祠中，點燃起篝火，裝作狐狸的鳴叫聲，呼喊道：
大—楚—興，陳—勝—王。
樹叢中神祠那邊，篝火閃閃，狐鳴淒切，士卒們無不感到恐懼；而“大楚興，陳勝王”六字人們也聽得清清楚楚。
第二天清晨，戍卒們對昨天早晨魚腹的帛書和夜間的篝火狐鳴，議論紛紛。一些認識與不認識陳勝的人，三三兩兩地指指點點，把視線投向陳勝。
陳勝、吳廣見群情騷動，認為時機已經成熟，決定立即采取行動。吳廣自被指派為屯長以來，一向體貼眾人，戍卒都樂意聽他的使喚。於是由吳廣出麵，趁著帶領戍卒的將尉喝醉酒的時候，吳廣故意多次揚言想要逃亡，以此來激怒將尉，令他當眾侮辱自己，來激起眾人的憤怒。將尉中計，果然鞭打吳廣。當將尉拔劍想要加害於吳廣時，吳廣眼疾手快，躍起奪過將尉手中的劍，隨即把將尉殺死。在吳廣奪劍時，陳勝向前佐助，合力將帶隊的兩個將尉當場殺死。戍卒們見將尉先是辱打吳廣，接著吳廣、陳勝奪劍殺死二將尉，無不驚得目瞪口呆。
陳勝、吳廣見二將尉已被殺死，戍卒騷動，便當即召集眾戍卒，大聲號召說：
“諸位因途遇大雨，大家都不能按期到達。按秦法，誤期的一律殺頭。即或是不被殺頭，因戍卒守邊而死的從來就十有六七。況且，壯士不死便罷，要死也得留下個大名聲。那些帝王將相，難道一個個都是天生的種嗎！”眾戍卒明知不能按期到達難免一死，見陳勝、吳廣已把將尉殺死，聯想昨日魚腹中的帛書和夜間的篝火狐鳴，對秦王朝的一腔怒火，被陳勝慷慨激昂的聲討所激起，覺得不如跟著陳、吳二人造反，也許會闖出一條生路；即或造反後戰死，死的也值得。所以眾戍卒們便異口同聲的回答：“甘願恭聽命令！”
於是，陳勝、吳廣便順應楚地人民的意願，冒稱是公子扶蘇、項燕，戍卒們都裸露右臂宣誓，號稱“大楚”。首倡反秦是件大事，為此還築起了高壇，陳勝、吳廣率眾人盟誓，替天行道，鏟除暴秦，生死與共，以兩個將尉的人頭祭祀天神。祭祀完畢，陳勝自立為將軍，吳廣為都尉，“斬木為兵，揭竿為旗”，攻占大澤鄉，直指蘄（今安徽宿州市東南）縣，沿途招收人馬，並攻占蘄縣縣城。
攻戰蘄縣後，陳勝令符離（今安徽宿縣東北）人葛嬰統兵攻占蘄縣以東地區。起義軍一路攻下銍（今安徽宿縣西南）、酂（今河南永城縣西）、苦（今河南鹿邑縣東10裏）、柘（今河南柘縣東北）、譙（今安徽亳縣）等諸多縣城。行進中沿途招收人馬，擴大隊伍，待到達陳縣（今河南淮陽）城下時，起義軍已有兵車六七百乘，騎兵千餘，步兵數萬人。義軍攻打陳縣（陳郡治所在陳縣）縣城，郡守、縣令都早已逃走，不敢留在城中，隻留下郡丞在譙門中抵抗，不勝而死，義軍攻占陳縣。
陳就是春秋時期陳國的都城宛丘，公元前278年秦將白起攻下楚都鄢郢，楚遷都於陳；公元前241年，楚由陳遷都於壽春。陳勝所率領的義軍在陳縣休整數日，號令在當地有聲望的三老（秦代每鄉置掌管教化的三老一人）、豪傑全部前來議事，三老、豪傑們都說：“將軍身披堅固鎧甲，手持銳利兵器，討伐無道，誅滅暴秦，重立楚國社稷，論功應立為王。”於是陳勝自立為王，號稱“張楚”，即張大楚國的意思。
自陳勝、吳廣在大澤鄉首倡反秦，於陳縣自立為王，天下各郡縣的百姓、豪傑苦於秦國地方官吏的橫征暴斂，濫用刑罰，紛紛起來懲罰當地的郡縣官吏，殺郡守縣令，起兵響應陳勝。由於起義軍勢力的迅猛發展，為適應形勢的需要，陳勝封吳廣為“假王”，暫時授予他代行王權的職位，率領眾將統兵西向攻擊重鎮滎陽（今河南滎陽縣東北）。同時，陳勝又令陳縣人武臣、張耳、陳餘北上攻占原趙國的領地；令汝陰（今安徽阜陽縣）人鄧宗攻占九江郡（治所在今安徽壽縣，轄今安徽，江蘇的長江以北、淮河以南及今江西省大部分地區）。當時，原楚國故地各支起義軍，人數在千人以上的不可勝數。
張耳是魏國大梁（今河南開封市西北）人，年少時是魏公子無忌的門客。後逃亡於外黃（今河南民權縣西北），當地一富豪把女兒嫁給他，女方以厚資使張耳得以招引來遠方賓客。張耳出任外黃縣縣令，賢名由此遠揚。陳餘也是大梁人，喜好儒家學術，多次遊學於趙國，知道他不是平庸之輩，當地一富豪把女兒嫁給了他。陳餘年少，在張耳麵前以侍奉父輩的禮節對待他，二人結成生死與共的刎頸之交。
秦軍滅魏時，張耳居於外黃縣，劉邦曾遊學於張耳，在那裏客居數月。秦滅魏數年之後，聞知張、陳為魏國名士，懸賞千金、五百金捉拿張耳、陳餘，二人變更姓名，一同逃往陳縣。在陳縣，二人充當裏門的守門人以糊口。裏中小吏因陳餘有小過而鞭打他，陳餘想起身反抗，張耳暗中踩他的腳，讓他忍受鞭打。小吏離去後，張耳把陳餘領到大桑樹下批評他說：“當初我怎麼對你說的，今日為什麼因受到一點小小的侮辱便忍受不住，想要與小吏拚死命。”陳餘覺得張耳的批評很對。有趣的是，秦懸賞捉拿張耳、陳餘的詔書，便是他二人以裏門看守的身份向裏中居民傳達的。
當陳勝率領數萬起義軍攻下陳縣後，張耳、陳餘前往陳勝軍帳，請求被接見。陳勝及左右的人早就聞聽過張、陳的大名，隻是未曾見過，因而非常高興地接見了他們。
陳縣的豪傑父老都勸說陳勝稱王，陳勝就此事詢問張耳、陳餘，二人回答說：
“秦國無道，滅亡他人的國家，毀壞別人的社稷，斷絕他人的後代，耗盡百姓的勞力，掠盡百姓的財產。今將軍義憤揚威，不顧一死為天下人除害，現在到達陳縣便稱王，向天下人顯示的是自己的私心。望將軍不要稱王，急速領兵西進，派人複立六國的後代，替自己樹立黨羽，給秦國多樹敵人。樹敵多則秦軍兵力分散，黨羽眾則自己兵力強大。如此則原野上無有交戰，郡縣中也會無人替秦守城，誅滅暴秦，據有鹹陽而號令諸侯。六國諸侯被秦滅亡後又複得立為王，以恩德使他們心服，如此稱帝於天下的大業可成。今日單單在陳縣稱王，恐怕天下諸侯會同您離心離德。”
陳勝沒有聽從二人的勸告，在陳縣自立為王。
陳餘在陳勝稱王後又進言說：“大王在魏、楚之地舉兵向西，進入關（指函穀關）中，顧不上派兵收複黃河以北趙國的地區。臣曾遊學於趙國，了解那裏的英雄豪傑及地理形勢，願請求撥給人馬，出奇兵北上攻取趙地。”於是，陳勝派過去同他要好的武臣為將軍，邵騷為“護軍”，負責調節各將領之間的關係；任命張耳、陳餘為職位僅次於將軍的左右校尉，撥給3000多步兵，北上攻取趙地。
武臣等人率兵從白馬（黃河渡口，舊址在今河南渭縣東北）渡河，所至各縣，首先向各縣的豪傑聲討秦的暴政，鼓動各地豪傑殺郡守縣令響應，並向百姓告知陳勝、吳廣已率大軍西向擊秦，是豪傑成就“封侯之業”的大好時機。各地豪傑認為武臣講得很對，武臣沿途招收人馬，擁有數萬名徒眾，“號武臣為武信君”，攻下趙地十餘座城池。其餘的城池都堅持同守，未能攻下。
武臣領兵向東北攻擊範陽（今河北徐水縣北），範陽的辯士蒯通向範陽令陳說諸侯叛秦，勢不可當，如果立即派他麵見武信君武臣，“可轉禍為福”。範陽令果然派蒯通見武臣，蒯通向武臣獻“不攻而降城，不戰而略地，傳檄而千裏定”的妙計，指出各縣城縣令堅守城池，是由於前十餘個縣令皆被誅殺，不敢投降義軍；如果賜給範陽令侯印，使他乘坐裝飾得富麗堂皇的車輛驅馳燕、趙故地，各地郡守、縣令見首先投降的範陽令受封為侯，定會爭相投降。武臣采納蒯通計謀，趙地有30餘座城池不戰而下。
葛嬰東向攻城略地到達東城（今安徽定遠縣東南50裏）時，立楚人襄強為楚王。後來葛嬰聞知陳勝已自立為王，便殺死襄強並返回陳縣報告此事。葛嬰到達陳縣後，因立襄強為楚王一事，被陳勝處死。
陳勝令部將魏人周市率兵北上攻占原魏國的故地。
吳廣率兵圍攻滎陽。滎陽是秦帝國三川郡治所，秦丞相李斯長子李由任三川郡郡守。在李由的固守下，吳廣未能攻下滎陽。陳勝征召國內的豪傑商討對策，任命上蔡（今河南上蔡縣西南）人房君為上柱國。上柱國在楚國是地位僅次於令尹（丞相）的官職，是楚國的最高武官。
周文，又名周章，陳縣人，是陳國的賢人，曾在楚國名將項燕的軍中任“視日”官，掌管占候卜筮、觀察天象以占卜吉凶，又稱“日官”。他曾侍奉過楚國春申君黃歇，是黃歇的門下客。此人自稱熟習軍事，陳勝授予他“將軍”大印，令他率大軍西向攻秦。周文沿途招收人馬，待到達函穀關（今河南靈寶西南）時，已擁有兵車千輛、步兵10萬人。周文率領的大軍抵達戲（即戲水，在今陝西臨潼縣東），駐紮於此，準備向秦都鹹陽發起總攻。這時，秦二世令少府章邯赦免驪山修墓刑徒和奴婢之子，率大軍攻擊周文，起義軍被打得大敗，東向逃出函穀關。章邯窮追不舍，於澠池（今河南澠池縣西）大破義軍，周文自殺，起義軍不戰而潰。
在陳勝派周文率大軍西進時，以為天下已經大亂，有輕視秦帝國的傾向，不再對秦軍有所防備。投奔陳勝的秦博士孔鮒，是孔子的八世孫，他向陳勝進言說：“臣聽兵法上講，不能依賴於敵軍不向我軍發起進攻，而是要依靠於我軍不可被敵軍攻破。今大王依賴於敵人的不來進攻而不依靠於我軍的不可攻破，如果一旦一蹶不振，後悔也來不及了。”
陳勝沒有采納孔鮒的意見，對孔鮒說：“寡人軍事方麵的事，就不必勞先生操心了。”
張耳、陳餘兵至趙都邯鄲（今河北邯鄲市），聞聽周文於戲水被秦軍打敗而退卻，又聞聽為陳勝四處攻城略地的諸將領歸還陳縣時，多因受讒言被誅殺，因而怨恨陳勝不采納他廣立六國的後代並率大軍西進的計策，對不任命他們二人為將軍而擔任校尉一事也深為不滿。於是，張耳、陳餘對武臣說：“陳王起兵於蘄縣，至陳縣便稱王，看來不一定會立六國的後代。今將軍僅以3000人馬攻下趙地十餘座城池，單獨被隔在黃河以北，不稱王便無法鎮守趙地。況且陳王聽信讒言，如果回去彙報請示，恐怕會難免於禍，不如立自己的兄弟為王，要不然就立趙國的後代為王，請將軍不要失去這一時機，時間緊迫，不容猶豫不決。”
武臣聽從張、陳的計謀，自立為趙王，任命陳餘為大將軍，張耳為右丞相，邵騷為左丞相。
武臣派人向陳勝報告稱王一事，陳勝大怒，想要把武臣留在陳縣的家屬全部誅殺，發兵攻擊趙王。陳勝的相國房君勸諫說：“秦尚未滅亡而誅殺武臣家屬，這等於又增加一個敵人，不如因此向他祝賀，令他急速率大軍西向擊秦。”陳勝聽從房君的計謀，把武臣的家屬軟禁在宮中，封張耳的兒子張敖為成都君。
陳勝派出的使者到達邯鄲，代表陳勝祝賀武臣稱王，同時令他率大軍西入函穀關擊秦。張耳、陳餘對趙王武臣說：“大王稱王於趙，並非是陳王本意，現在是出於權宜之計表示祝賀。一旦陳王滅秦，必定加兵於趙。願大王不要西向出兵，而是北上攻占燕、代，向南攻占黃河以北地區以擴大領土。趙南據有河內，北有燕、代，如此即或是楚兵滅秦，也不敢製服趙國。”
趙王認為二人講得很對，便不發兵向西，而是派韓廣北上攻占燕地，派李良出擊常山（秦郡名，治所在元氏，今河北元氏縣西北），派張槭攻占上黨（秦郡名，治所在壺關，今山西長治市北）。
陳勝、吳廣自秦二世元年（前209年）七月於大澤鄉起義，至同年九月，在兩個月之中，以陳勝為首的這支起義軍勢力迅速壯大。由陳勝向東、西、北三麵所派出的各路義軍，占領了秦帝國東土上的大片土地，有的還自稱為王。昔日強盛一時的秦王朝，現在已經搖搖欲墜了。
在這種此起彼伏的各地起義形勢下，沛縣縣令感到非常恐慌。因為沛縣地處南北要衝，地理位置十分重要，是兵家必爭之地，而且陳勝、吳廣起義軍近在咫尺，他們隻要派一支偏師就可即刻攻至城下，那麼自己將會成為起義軍的刀下之鬼。因此他想在沛縣主動起義，響應陳勝、吳廣。但他自己又是秦朝中央政府委派的地方官吏，萬一起義失利，則這種大逆不道的罪行將會使自己的大好前途葬送殆盡，而且將會落個滿門抄斬、斷子絕孫的下場。
這樣考慮來考慮去，幾天幾夜不能拿定主意。這時他突然想起他的重要助手——蕭何。蕭何這個人一向以辦事謹慎、明辨事非、有方略而著稱，何不把他召來，看看他的意見如何？
於是縣令連夜派人火速召來蕭何和曹參，商量對策，說：“陳勝、吳廣舉事以來，銳不可當，各地郡縣紛紛舉事響應，你們看他們這些人會成功嗎？”
蕭何、曹參知道縣令現在拿不定主意，於是蕭何對縣令說：“秦朝滅亡是早晚的事，俗話說：‘識時務者為俊傑’，大人必須早拿主意啊！”
縣令點了點頭，說：“依你看，我現在該怎麼辦？”
蕭何和曹參明白，縣令是在搞政治投機。縣令素來反複無常，首鼠兩端，跟著他造反，肯定成不了什麼氣候。在兩人的心目中，劉邦才是真正的英雄。
他們委婉地說：“主公是秦朝的命官，過去總是要求大家忠於朝廷，現在又突然宣布起義，沛縣城裏的百姓，會俯首帖耳聽您的指揮嗎？隻怕事情還未成功，主公的腦袋就……”
兩人的話還沒有說完，縣令已經冷汗淋淋，顫抖著聲音問：“那……那該怎麼辦呢？”
蕭何摸了摸胡須，裝作認真思考的樣子，過了好大一會兒，才說：“辦法倒是有一個，就怕您不會同意。”
縣令早已急不可待，催促蕭何快說。
蕭何提了提神，一字一板地說：“隻要主公把犯了秦律，被迫逃亡在外的人都請回來，那就有好幾百人。有這幾百個人給您撐腰壓陣，縣衙裏的人，誰敢不聽指揮。”
縣令聽出了蕭何話裏的真意，是要他把劉邦請回來。他盡管心裏很不高興，可眼下又沒有更好的辦法，隻好抖抖索索地給劉邦寫了一封信，約請劉邦下山舉事，並具體委托蕭何辦理。
在沛縣殺狗賣肉的樊噲，娶了呂雉的妹妹為妻，和劉邦成了親戚。劉邦上了芒、碭，他成為劉邦和蕭何之間的聯絡官，常常為劉邦通風報信。蕭何把縣令的信交給樊噲，自己擬了個裏應外合的計策，讓樊噲立即上芒、碭去找劉邦。