萧何见到刘邦，立刻告诉他县令反悔的变故，现在城门已被封闭，可能需要从长计议。但刘邦只是微笑点头，下令继续向县城前进。

原来刘邦早已让樊哙先回城，由留居城中的心腹煽动沛县父老策动兵变。现在既然县城的萧何等人都已经站到刘邦的阵营里来，这场争斗，他们已经掌握绝对优势了。萧何见刘邦经过这几年磨练，已有了大将的才干，心中十分高兴，决心从今以后跟随刘邦创一番大事业。

刘邦等人来到城门下，只见城门紧闭，戒备森严。萧何建议刘邦亲自在帛上书写几十封信，并将信系在箭捎上射进城内。射出的书帛虽然大多有守城兵士交给县令处理，但还是有几分落到沛县父老的手中，书信上这样写着：“天下老百姓被秦王朝的苛政害得很苦，现在各地都起兵抗秦，沛县父老们不如响应义军，擒杀县令，和各路诸侯站在同一战线，这才是保家卫城之道。如果父老子弟们和县令站在一起为腐败的秦朝卖命，那是很不值得的！”这些书信有意制造县令和沛县父老们的矛盾。果然县令大惊，立刻在城内实施严格军管。父老们本来就对秦王朝十分痛恨，现在看到县令这样顽固的抵抗起义队伍，根本就不支持县令。

樊哙等人一不做二不休，当晚就发动沛县民众造反，原来在县府守卫的子弟兵也纷纷响应。县令孤掌难鸣，当他得知民众们暴动时，赶紧丢了官服逃走，可他还没来得及逃到城外，就被一群乱民杀死了。

樊哙率领的人马很快占据了沛县县城，他下令打开城门，迎接刘邦的队伍入城。沛县父老们夹道欢迎，大家拥着刘邦进入县衙，恳切的请求刘邦出任县令。刘邦一再推辞，谦让的说：“如今天下大乱，四方诸侯并起，斗争相当激烈，选择首领若不适合，会给大家带来灾难。我怕自己的才能不足以担当这个重任，大家还是另外选择更好的领导人物吧！”沛县民众全力拥护刘邦，一再要求由他出面领导，父老恳切的说：“我们早就相信你会成为贵人，依照前天占卜的结果，只有你担任领袖最吉利，请你就不要客气了，沛县的安危，从今天起全在你手中了。”刘邦谦让了几次，眼见众命难违，同时大家都充满诚意，就接受了大家的推荐，承担起领导人的任务。

但刘邦最高的官位只是个小亭长，如今跃升为全县的首领，到底如何来称呼他好呢？萧何想了想，向刘邦建议说：“以后咱们就叫你沛公吧，现在你是沛地的领袖，又有贵族的气派，这个称呼再合适不过了。”刘邦觉得这称呼很好，就采纳了萧何的建议，从此，刘邦成了沛县的首领，大家称他为沛公。

刘邦在沛县起兵以后，又召集了两三千人，占了自己的家乡丰乡。刘邦决定重新整编人马，现在他手下沛县的子弟兵总共有3000多人。刘邦让大家换上全新的戎装，排列在县衙大门广场上，准备亲自检阅一次。刘邦先到大庙祷告黄帝，又在广场祭祀战神。接着，他下令敲响战鼓，把所有的旗帜都染成红色，阵容还算很壮大。

经过一番考虑，刘邦决定任萧何和曹参为主要参谋，卢绾为侍从官，夏侯婴、任敖、周勃、灌婴为部将，另外，他还特意把勇猛的樊哙任命为全军的先锋，并将大本营暂时设在自己的故乡丰乡，这样，刘邦拥有了一支具有相当实力的队伍。