于是，关于刘邦的种种神奇的传言迅速传开，许多老百姓都相信他是赤帝之子，是真命天子而愿意归顺他，刘邦也乐于接纳各种力量，他率领队伍游荡于芒、砀的山泽之间，势力一步步壮大起来，他也因此被当地人称为沛中的豪杰。
这时候，以陈胜、吴广为主的各地反秦力量风起云涌，气势越来越高涨，沛县的县令也想响应起义军来保全自己，他的手下萧何和曹参就向他建议说：“大人是秦朝的官员，现在想反抗秦朝，领着沛中弟子起兵，恐怕难以服众。依属下看，大人最好把那些逃亡在外的人召集回来，这样就能聚集几百人，大家就会有所依附，自然就听您的了。”县令听后觉得很有道理，就表示同意，并且派刘邦的连襟樊哙去请刘邦。但是，还没有等到刘邦进城，县令就后悔了，他早就听说了刘邦斩白蛇的故事，害怕刘邦一旦入城之后会难以控制，众人拥戴刘邦而不拥戴自己。于是，县令下令城门紧闭，不让刘邦入城，并阴谋借机杀死萧何、曹参等人。萧何、曹参闻讯后，纷纷逃出城去与刘邦会合。当时为刘邦驾车的，就是他的老朋友夏侯婴，看来跑出沛县投靠刘邦的吏员，还不止曹参与萧何两人。这时沛县的县令已动员各里社父老统领子弟跑上城头备战。刘邦没有下达攻城令，而是写了一篇致父老的布告，用羽箭射上城头。布告称：天下人苦于秦朝很久了！现在父老们为沛令守城，等群雄并起而攻，势必屠戮全城生灵。假如今天沛人一起杀了沛令，从子弟中选择一个可推举为首领的人，响应群雄，那么大家都可以保全家园。不然，父老子弟都遭屠戮，这是没有必要的。
父老们传阅了刘邦的布告，都认为他说得在理，便率领子弟们一起将这位出尔反尔且平时就不体恤百姓的县令杀死，打开城门，迎接刘邦进城。可以设想，卢绾的父亲，吕雉的父亲，以及卢绾、周勃、奚涓、纪信等一批刘邦的同伙和好友，都在这起政变中发挥了鼓动和带头作用。
接着，萧何和沛县的百姓们决定一起推举刘邦做县令，刘邦心里暗自高兴，嘴上却推辞说：“天下形势纷扰，群雄并起，假如现在没有安排妥善，一朝破败，就会肝脑涂地。我刘季无德无能，恐怕难以胜任。拥立首领是大事，大家还是推举更有德行的人吧。”
沛县的百姓齐声说：“我们早就听说了你的事情了，你是大贵之人，不用推辞了！”于是刘邦称沛公，在县衙里树起大旗祭天地，并宣布自己是赤帝之子，奉天命诛无道之秦，正式宣布反秦。在萧何、曹参、樊哙等人的辅佐下，刘邦逐渐站稳了脚跟，他正式进入了秦末群雄逐鹿的政治、军事斗争当中，这一年是秦二世元年的九月，刘邦已经48岁了。
在刘邦起兵反秦后，秦末农民起义战争已经进行得如火如荼。陈胜和吴广的起义，是反抗暴政的先锋，可惜他们的军力弱小，无法抵抗秦军，而自己又内讧迭起，不久就溃不成军。
公元前208年，陈胜起义军在渑池（今河南渑池县）遭到秦朝大将章邯所率军队的镇压。陈胜部将大多战死，吴广被叛徒田臧杀害。陈胜从陈郡败走，退到下城父（今安徽涡阳东南），被车夫庄贾杀害。陈、吴的起义宣告失败。这时，项羽和他的叔父项梁以8000兵从江东之地出发，渡过长江北上，准备进攻薛地，同时在各地的义军也纷纷响应，顿时项军成了几十万的大军团，也就成为各地起义军的中心。
刘邦在沛县起义后，不停地攻打邻近的各县，和秦军展开了一进一退的拉锯战。到了公元前208年的4月，刘邦到薛地拜访项梁，决定和项梁会军共同抗秦，因而成了项梁军下的一个支队。由于这次的会合，刘邦的军团强化了许多，而更值得庆幸的事是，刘邦得到了一个军师——张良。张良精于“太公兵法”，给刘邦提供了很多的战略指导，对于刘邦能得天下，功不可没。
刘邦加入项军两个月之后，项梁接受了谋臣范增的献策，找到了一位叫做“熊心”的曾被秦所灭的楚王的血亲，让他登上王位，即为楚怀王，以他作为各义军的盟主。此时，刘邦的军队，也增加到一万四千多人，他正应和着项梁准备攻打咸阳。
与此同时，秦将章邯已经攻灭了魏国和齐国。到了公元前208年7月，楚军经过休整，开始向秦国反攻。楚军连连胜利，项梁被胜利冲昏了头脑，骄傲起来，已经听不进别人的进谏了。9月，章邯得到秦国关中的援兵后，乘项梁不备，突然夜袭定陶。结果楚军大败，项梁也不幸阵亡。
由于楚军续战不利，不得不缩小战区，采取守势，秦军却趁着战胜的余威，一路北上攻陷了赵国的都城——邯郸，且将赵王歇及张耳等义军逼至巨鹿。此时，楚怀王只得撤退到彭城，准备重整旗鼓，而巨鹿的赵军也频频地派人来，要求怀王派军支持赵国抗秦。
由于时势的紧迫，公元前208年的闰九月，各地反秦的首领在楚国的都城彭城召开了一次决定性的战略会议，在席上他们决定将义军分兵两路：一路以宋义为上将军，项羽为副将，范增为末将，北上救赵，解赵王的燃眉之急；一路以刘邦为将，西进关中，进攻咸阳。在军队要出发之前，楚怀王对各将领宣布说：“谁能先平定关中（咸阳一带），就封他为关中之王。”
当时，项羽提出和刘邦一起西进关中，为叔父报仇，却遭到了一些谋士、老臣的反对，他们认为，项羽处事冲动、手段残忍，既年轻又没有经验；而刘邦是个长者，宽厚仁慈，威望较高。所以，决定只让刘邦一个人统兵西进。
开始时，刘邦也进行得不太顺利，但经过连番征战，刘邦步步西进，攻入武关，向咸阳逼近，最后终于兵临城下。秦相赵高逼死秦二世，派人向刘邦求和，被刘邦拒绝。秦王子婴即位后，诛灭赵高，并派兵在蛲关抵挡刘邦。刘邦率军绕过蛲关大破秦军，进抵咸阳东郊霸上。秦王子婴见大势已去，被迫捧着玉玺向刘邦献城投降，秦王朝至此灭亡。
子婴投降后，刘邦的部将多数主张诛杀子婴，而刘邦却说：“楚怀王之所以派我西征是因为他知道我这个人仁慈宽厚、胸怀广大，何况现在敌人已降服，我再杀了他，又有什么好处呢？”因此，刘邦只派人监视着子婴，而没有杀他。
立足关中，约法三章
刘邦以胜利者的姿态得意洋洋地进入了咸阳城，并以“关中王”自居。他走进了秦王富丽堂皇的宫殿，满眼都是豪华的帷帐，硕大肥壮的犬马，灿烂耀目的金银宝石，光彩怡人的嫔妃、宫女，这使得穷苦农家出身的刘邦，不由得瞠目结舌。刘邦有些留恋起来，准备就此住下，尽情享受。樊哙知道了刘邦的心意后，劝他以安定天下为重，别忘了暴秦的前车之鉴，可此时的刘邦根本听不进去。樊哙无奈，只好找来了张良。张良劝刘邦说：“今天的局势，是因秦王无道，所以主公才能到这地方来，你若还未忘记自己的志愿，想为天下老百姓除害、歼灭残贼，你就只能过一种布衣粗食的生活，你现在若因攻陷了咸阳，就自大自满地过着挥霍无度的日子，必定有人会说你的行为远超过夏桀的暴虐，到那时你的功名成就即将毁于一旦。俗谚云：‘忠言逆耳而利于行，良药苦口而利于病。’请你无论如何不要在咸阳长住。”张良的一番话使刘邦恍然大悟，他这才认识到了问题的严重性。虽然心中舍不得这繁花似锦的咸阳城，还是听了大家的话，退兵到霸上扎营，准备以后的战事。
到了霸上，刘邦召集了各县的父老及富绅，发布了着名的“约法三章”。刘邦对他们说：“各位关中的父老乡亲们，大家对秦王朝的严刑苛法，都已经身受其苦很久了。我和全体起义的诸侯有共同的约定，先进入关中者就可以称王，因此我是公认的最有资格成为关中王的人。现在我以王的身份和父老们约定，订立三个最基本的维持治安的法律：从现在起，无论任何理由，杀人者判处死刑，伤人和抢夺盗窃的也依情节轻重处以应得之罪。至于其余秦法全部废除，所有官吏及民众的地位、工作和生活习俗，一切如常。我今天到这里来是为父老除去生活疾苦，不是来欺负和抢夺你们的，所以大家不用恐惧惊慌。为了不打扰百姓，我下令所有军队撤回到霸上，并等待其他诸侯军队到来，重订统治管理的办法！”
于是刘邦又使人巡回各县乡邑，张贴布告，把约法三章告谕众民，其他的西征军团将领看出刘邦维持军纪的决心，也不敢再轻举妄动了，关中地方很快恢复了秩序。那些苦于秦朝苛政的人民一听“约法三章”，也都齐声欢呼，争先持牛羊酒食来犒劳沛公的军士，唯恐刘邦不能留在秦地为王。萧何便告诫刘邦不要接受，以充分表示爱民和不扰民的决心。于是刘邦抚慰前来劳军的秦国大老说：“我们军队的精粮很多，若不缺乏，绝不劳民，你们自己好好保存起来吧！”秦民因而更感其恩德。
于是，便有人对刘邦说：“关中这地方有天下十倍那么富，地形也险要。听说秦朝大将章邯投降了项羽，项羽封他为雍王，做秦地的王。他如果来了，您就做不成关中王了。不如派兵把守函谷关，不让诸侯的兵进来，您征集关中的兵来补强自己就可以了。”刘邦听信了他的话，就派兵把守函谷关。尽管这一决定差点使刘邦和项羽兵戎相见，以致在鸿门宴上死里逃生，但足以证明刘邦的约法三章极大地收买了人心。
从撤出咸阳，到宣布约法三章，刘邦的表现都非常高明，对于人心的收揽更是超人一等，此时刘邦的军队，已从游侠的集团蜕变为一支强而有力的军队，渐渐也有逐鹿天下的实力和基础。
鸿门宴“项庄舞剑”
项羽在救赵取得消灭秦军主力的胜利后，也率军直奔关中，以争夺做天下王的资格。等来到函谷关，项羽见城门紧闭，又听说刘邦已平定关中，不由大怒，当即命英布攻破函谷关，亲率四十万大军直奔咸阳，开到戏下（今陕西临潼东北戏水西岸）驻扎下来。
这时，刘邦的左司马曹无伤暗中派人向项羽告状说：“沛公欲在关中称王，想让子婴做相国，把秦国的珍宝都据为己有。”项羽一听不由得火冒三丈，其手下谋士范增也向项羽献计说：“刘邦从前住在山东的时候，贪财好色，现在入了关中，丝毫不取，连妇女都不屑一顾，可见他胸怀大志，绝对不寻常。我曾命手下相命之士观望沛公的气，见其气呈龙虎五彩之象，这乃是天子之气。现已刻不容缓，请赶快攻击刘邦，一举灭之，千万不要延误时机。”
于是，项羽下令犒劳士兵，明天一早就向刘邦进攻。此时，项羽有兵四十万，驻守在新丰鸿门。而刘邦当时只有十万人，在兵力上完全处于劣势。大难就要临头之际，刘邦却迎来了一个救星。这个救星就是项羽的叔叔项伯。项伯和刘邦的谋臣张良交往甚密，张良曾救过他的命。项伯听说马上就要向刘邦进攻，就连夜驰入刘邦军中，想把张良带走。张良却对他说：“沛公有大难，我作为谋臣不能一声不吭就走，要走也得把这个事情告诉他。”刘邦听了大惊，要张良赶快考虑对策。张良让刘邦赶紧去约见项伯，说明自己没有野心和项羽争夺王位。
刘邦遂以对待兄长的礼仪设宴款待项伯，并说愿与项伯结为儿女亲家。他对项伯说：“我进入关中，一点东西都不敢据为己有，登记了官吏、百姓，封闭了仓库，等待将军到来。派遣将领把守函谷关是为了防备其他盗贼的出入和意外的变故。我日夜盼望将军到来，怎么会有造反之心呢？请您回去务必向项羽将军说明此事，消除误会。”项伯满口答应，然后对刘邦说：“将军你明天一定要到我们的营帐亲自向项将军说明情况，当面赔礼，才能得到原谅。”刘邦听了也答应了。
项伯当天夜里就返回了军营，他对项羽说：“因为沛公先行进入关中，为我们扫除了入关的障碍，我们这才能顺利地通过函谷关，人家是功臣，你要加害功臣，这是不义之举。况且，人家对财物妇女一律不取，连降王子婴也没有擅自发落，就等你前往共同处置呢！刘邦明天前来当面谢罪，你不如就此与他修好。”项羽听了，便决定不再进攻刘邦。
第二天，刘邦只带了樊哙、张良和100名精锐亲兵，如约来到了项羽的军营。在项羽的大帐鸿门，刘邦十分谦恭，见了项羽便下拜：“未知将军入关，有失远迎，今天特地上门谢罪。”并开诚布公地相告：“我和将军并力攻打秦国，将军在黄河以北作战，我在黄河以南作战，但是我自己没有料到能先进入关中，灭掉秦朝，除了与民约法三章，一切照常。眼下定是有小人散布谣言，从中挑拨，使您和我发生误会。”项羽说：“这是您的左司马曹无伤说的，不如此，我怎么会这样。”
项羽请刘邦入内赴宴，在酒宴上，刘邦、项羽与群臣共饮，范增屡次使眼色示意项羽杀刘邦，又举所佩带的玉环，以示意项羽杀掉刘邦，连做了三次，项羽却默然，无任何反应。范增看情形不对，起身到外召来项羽的堂弟项庄，请他借舞剑为名，借机刺杀刘邦，这就是“项庄舞剑，意在沛公”。此时项伯看出了他的心意，也拔剑起舞，在二人舞剑时，项伯不时地用自己的身体掩蔽刘邦，酒席中酝酿着一触即发的危机。
张良看情形不对，连忙起身到帐外，找到樊哙，樊哙即刻带了宝剑，拿了盾冲入帐内，睁眼怒视项羽，项羽为之一惊，大声问道：“来客是什么人？”张良代替樊哙回答：“这是沛公的随从，叫樊哙。”项羽说：“真是壮士，赐他酒喝。”便有人送酒、肉到樊哙面前，樊哙一点也不畏惧，一口气喝干了酒，又拔出剑来，在盾上切猪肉，一大块一大块地吃着，项羽又赐他酒喝，之后他便整装端坐对项羽说明沛公并无谋反之心，项羽听后默然不语。
稍过一会，刘邦见情势更为紧张，便起身以小解为借口，离开项羽的大帐，随即在樊哙等人的保护下抄小路回到霸上军营，这便是历史上有名的鸿门宴，也揭开了刘邦与项羽对峙的序幕。
刘邦走后，张良估计沛公可能已回到军中，便进帐向项羽告罪，捧上白璧献给项羽，又献玉斗给范增。范增知道刘邦已离开，心中大怒，拿起玉斗放在地上，拔剑一击，玉斗粉碎。范增又恨又怒地叹息说：“唉！这小子不值得和他共谋大事！将来夺取天下的人一定是沛公。我们这班人就要被他俘虏了！”
