刘邦作为一个亭长，其中一项重要的工作就是为县里押送刑徒前往骊山，帮助修筑秦始皇陵。在一次押解途中，很多刑徒都趁机逃跑了。刘邦很着急，心里估计到骊山时，刑徒们可能都跑光了。按照秦律，如果刑徒逃跑，押送的人要被处死。反正都是一死，刘邦觉得还不如放了这些刑徒，也算是功德一件。等走到丰邑的一处沼泽时，他就趁着夜色就把剩下的刑徒全部释放了。
他对剩下的刑徒说：“各位都走吧，从此以后我也不再回去了。”剩下的刑徒里有十几个壮士，本来是准备逃跑的，但听见刘邦要放他们走，他们放弃了离开。他们决定留下来跟着刘邦。这些人聚在一起商议：此时回家是不可能了，一回去肯定会被当地官员抓起来问罪。经过讨论，他们发现只有一条生路：去芒砀山（在今河南省永城市境内）落草为寇。
这一群人在商定了主意之后，便喝酒盟誓。酒一下肚，刘邦就开始想像去芒砀山的快乐生活。当下便决定连夜径直穿过沼泽，让一个人在前面探路。不一会，这个探路人回来报告说：“前面有一条大蛇挡在路上，无法通行。”刘邦此时还正在酒劲上，说：“壮士走路，怕什么！”也是他一个人上前，而剩下的人都因为害怕留在原地。
刘邦借着酒劲，上前探路，看见大蛇，直接拔剑上前去砍，蛇一下子就被砍成了两段，道路一下子就畅通了。又向前走了几里，因为醉酒，便躺在地上睡着了。后面的人因为久久没有看到刘邦回来，便一起壮着胆子向前走，等走到大蛇出现的地方时，看见了一个老妇人在路边哭泣，人们问他为什么在夜里哭泣。老妇说：“有人杀了我的儿子，所以我在这里哭。”众人愈发好奇：“你的儿子为什么被杀呀？”老妇回答说：“我的儿子是白帝之子，变化为蛇，挡在路上，今天被赤帝的儿子砍成两段，因此我在这里哭。”
众人都觉得老妇是在说胡话，于是便想上前围攻老妇，可是，就在围攻时，老妇人却突然不见了。于是，众人继续向前走，叫醒在路上睡着的刘邦，把这件事情告诉他。刘邦一听，心中暗暗高兴，自以为自己很不寻常。而那些跟随他的人经过这件事情之后，就越来越敬重他。
当时的国家正处在秦始皇的统治时期。秦始皇经常说：“东南方有天子气”，于是就通过巡游东方，想通过天子的威仪来镇压那里的天子之气。而刘邦在芒砀山落草为寇后，他的妻子吕雉寻找他时，总能精确的找到刘邦的位置。刘邦很奇怪，询问吕雉原因，吕雉说：“你所在之处的上方总有云气聚集，所以跟着云气走就会找到你。”刘邦听了之后，认为自己身上有天子气，心里非常高兴。沛县的子弟，们听说这件事后，大多数人都想要追随刘邦。
秦二世元年（前209年）秋季，陈胜等人起兵反秦，来到陈县自立为王，号称“张楚”。此时各地的百姓都杀死当地长官来响应陈胜。沛县县令很害怕当地的百姓效仿其他的郡县百姓杀死他来响应陈胜。于是，想要带头反叛，响应陈胜。主吏（主要掌管县里的政事）萧何、狱掾（主要掌管县里的司法和刑狱）曹参对县令说：“您担任秦朝的官员，现在却要背叛秦朝，率领沛县的子弟起兵，恐怕他们不会听从。希望您可以召回那些在外逃亡的人，这样的话，就能够得到几百人，利用他们来胁迫众人，那么众人就不敢不听从了。”
那么问题来了，那么多逃亡的人，应该把谁召回来了呢？这个问题毋庸置疑，当然是影响力最大的刘邦。于是县令便派樊哙去芒砀山接刘邦回沛县。等到刘邦快要回来时，县令却突然后悔了，就关闭城门，加强进入县城的道路。并且想要诛杀萧何、曹参。萧何，曹参很害怕，就翻越城墙投靠刘邦自保。
刘邦为堵在城外进不了城，于是在丝帛上写了一封信射入城中，告诉沛县的父老说：“天下人深受秦的暴政折磨已经很久了。现在父老为县令守城，可是天下的诸侯都已经起兵反抗秦朝，到时候就要屠戮沛县了。现在沛县的父老一起诛杀县令，选出可以担任首领的子弟推举他，以此来响应诸侯，只有这样才能保全身家性命。否则，父子都会被诛杀，等到了那时候，大家就只能是白白丧命了。”
有刘邦这封书信的劝说，沛县的父老于是就率领子弟们一起杀死了沛县县令，打开城门迎接刘邦。想让他当沛县县令。刘邦回绝说：“天下正陷入混乱，诸侯们都起兵反抗秦朝，现在选出的将领不称职，就一败涂地了。我不敢吝惜自己的性命，只怕自己才能浅薄，不能保全沛县父老子弟的性命。这是大事，希望另选一位合适的人。”此时，除了刘邦之外，沛县有影响力的人还有两个，分别是萧何、曹参。他们都在沛县的县里当官，在当地有一定的威望。如果让他们当县令，必定能够服众。
可是，萧何，曹参都是文吏，吝惜自己的性命。害怕事情不成功，如果自己领头，事情万一不成功的话，秦必定会将他们灭族。有此担心，他们两人就没有当县令的念头。便一起推举刘邦。众人也都劝刘邦说：“我们平时都听说刘季的奇异之事，刘季必定得到富贵，况且经过占卜，没有人比刘季更合适了。”
刘邦仍然多次谦让，可是众人都不敢担当。大家一致推举刘邦当沛县的县令，组织起义。于是刘邦无法推辞，只得接受。此时，起义的诸侯纷纷都自立为王，刘邦也想称王，但害怕吸引到秦军的攻打，于是降一级，自立为沛公。不仅如此，他还给自己起了个响当当的名字——刘邦。
于是刘邦就在沛县的官署内祭祀黄帝，先祖，把牲畜的血涂在旗子上，将旗帜都染成红色。为什么是红色呢？因为当初刘邦所杀的蛇是白帝之子，杀蛇的是赤帝之子，因此崇尚红色。沛县的少年和有权势的官员都帮助刘邦招兵买马，很快得到二三千人，开始着手攻打周边地区。
这一年是公元前209年，这一年刘邦四十七岁，也是在这一年，刘季变成了刘邦，泗水亭长变成了沛公。
