沛公刘邦接受了怀王心入关破秦的命令后，就率领近万人的队伍，离开彭城，浩浩荡荡朝西而去，沿途收编了陈胜、项梁的残部，合并了其他一些反秦武装，队伍逐渐壮大起来。秦二世三年（前207）二月，刘邦乘巨鹿决战之机，由砀（今河南永城东北）率军北上。在攻打昌邑（今山东巨野南）时，刘邦又遇到了坚持抗秦的起义领袖彭越。
彭越是昌邑人，常年在巨野泽中捕鱼。他为人豪爽，精明强干，在当地有很高的威信。当陈胜、项梁揭竿起义的消息传到昌邑一带时，一些穷苦弟兄就找到彭越说：“许多英雄豪杰背叛暴秦，占地为王，你怎么还有这闲心捕鱼呢？也带领大伙造反吧！”彭越一时拿不定主意，没有答应。过了一年多，反秦的烈火遍地燃烧，昌邑一百多年轻人相聚到一起，又找到彭越说：“不要再等了，你就赶快带领我们造反吧！”
彭越推辞说：“造反可以，只是我年纪大了，不宜当头。”
“你德高望重，说话顶事，我们都听你的。”年轻人七嘴八舌地说。
“那好。”彭越终于答应下来，“明天早晨日出时在泽边会合，迟到的就要杀头。”
不料第二天集合时，迟到的竟有十几个人，其中一人，直到午时才赶到。彭越满面怒容，严厉地说道：“起兵造反，非同小可，必须有严密的组织和纪律。可是第一天，就有这么多人迟到，这怎么行军打仗？我已有言在前，迟到的要杀头，但又不能把这么多迟到的全杀掉，只好杀最后到的吧！”
众人一听，吓得目瞪口呆，纷纷为那人求情。
彭越说：“既然大伙推举我当头领，就得听我的！”说罢，便将那人的头砍下，然后摆设祭坛，宣誓起义，明确军纪。从此，一支纪律严明的起义队伍，就开始活跃在昌邑一带了。如今，彭越见刘邦率领着大部队来到此地，喜出望外，答应愿做前导，攻打昌邑城。
这昌邑在荷水之滨，北边就是港汊纵横、水波连天的巨野泽，也是彭越起义军的根据地。所以昌邑城虽然不大，但出于对起义军的防范，城墙相当坚固；城中的秦军在连遭起义军袭击的过程中，也得到了锻炼，有着严密的组织。彭越满以为这次借助刘邦大军的力量，攻破昌邑，能使自己有一块稳固的地盘，不料连攻几次，城中的秦军只是顽强固守，坚不出战，使起义军占领昌邑的计划未能实现。
刘邦见昌邑难以攻破，便对彭越说：“我的任务是入关破秦。昌邑城虽然没有攻破，但遭此打击，守军只能龟缩在城中，对我的西征不再构成威胁。现在我就要起程了。”
彭越含着热泪，依依不舍地说：“昌邑的秦军有我监视，将军只管放心西去，后会有期。”后来彭越的队伍发展到一万多人，在楚汉战争中，成为汉王刘邦的重要盟友，特别是在垓下之战中，配合刘邦，大破楚军，迫使项羽自杀。刘邦称帝后，封彭越为梁王，以定陶为都城——此是后话不提。
且说刘邦辞别了彭越，向西攻打陈留时，遇到了一位六十多岁的书生——郦食其。
郦食其是陈留高阳人，虽家境贫穷，仍嗜酒如命，人称高阳酒徒。他喜读书，性豁达，又被称作狂生。其实，郦食其是个很有心计的人。他对残暴的秦王朝恨之入骨，对奋起抗秦的陈胜、项梁寄予很大期望，可是当陈胜、项梁率领部队先后路过高阳时，郦食其发现他们心胸狭窄，不足为交，因此隐居未出。如今刘邦为攻打陈留，驻在了高阳，他要了解一下刘邦是怎样一个人。恰好刘邦的马夫是郦食其的同乡，于是郦食其便向那马夫问道：“沛公那人怎样？”
那马夫答道：“沛公抱负大，胸襟宽，智谋广，喜结交。每到一地，他总爱打听那里有什么豪杰贤士。”
郦食其一听，高兴地说：“我就喜欢这样的人。你快去告诉他，就说本地有位郦先生，六十多岁，身长八尺，很愿意见他一面。”
那马夫说：“沛公虽喜结交，但态度傲慢，尤其看不起读书人。以往有些儒生戴着帽子来拜见他，他就把人家的帽子摘下来，当便盆用。跟人谈话时，他也是出言粗鲁，骂骂咧咧。如想见面，最好不说你是读书人。”
郦食其说：“没关系，你只管照直说就是了。”
果然不出马夫所料。刘邦听说一个六十多岁的老书生要见他，便摇摇头说：“告诉那老头子，老子现正忙于打仗，不见儒生！”
郦食其一听，气得火冒三丈，又对那马夫说：“你再回去告诉他，就说那老头子不是儒生，是高阳酒徒。”这一着还真灵，那马夫这么一说，刘邦果然让他进去了。郦食其来到军帐，见刘邦正高傲地坐着，让两个年轻女子给他洗脚。他看见郦食其进来后，只欠了欠身子，连站也没站起来迎接。郦食其见刘邦如此傲慢，便故意问道：“你是打算帮助暴秦攻打诸侯呢，还是打算率领诸侯攻打暴秦？”
刘邦听了反口大骂：“你这个书呆子，真是岂有此理！全国百姓不堪忍受暴秦的残酷统治，早就想推翻它，各地诸侯才相继起兵，你怎么敢胡诌，说我想帮助暴秦打诸侯呢？”
郦食其说：“既然你想推翻暴秦，夺取天下，就不应该这样对待长者。”
刘邦一听，感到这位老先生是个有作为的人，就赶快穿上鞋，把衣服整理好，恭恭敬敬地请郦食其坐到上座，虚心地向他请教。
郦食其看到刘邦挺能接受意见，就劝告刘邦说：“将军带的这支队伍，是从四面八方凑起来的，而且总共也不过一万多人。用这样的队伍去攻打强大的秦王朝，不是等于拿鸡蛋去碰石头吗？”
刘邦忙问：“那该怎么办呢？”
郦食其想了想，说：“陈留这个地方，四通八达，是交通要道，城里又有许多粮食。我和陈留县令有交情，可去劝他投降；他如果不听，将军就从外面攻，我在里面做内应，占了陈留，就可有个立脚之地了。”
刘邦采纳了郦食其的建议，果然没费一兵一卒就占领了陈留，得到了很多粮食。刘邦对郦食其很满意，就给了他一个“旷野君”的称号。
郦食其的弟弟郦商，在当地有一支四千人的队伍，经郦食其说服，也投奔了刘邦。刘邦委派他做副将，统领陈留兵马。郦食其就留在刘邦身边，出谋划策。
刘邦占领了陈留以后，正向开封进发，张良突然率部赶来。二人久别重逢，格外高兴。
原来，张良自从征得楚将项梁的同意，拥立了韩王成，带领一千多人马离开楚军大本营后，就来到旧时的韩国地界，转战于颍川一带。时间不长，张良的队伍就发展到一万多人，有力地牵制着韩地的秦军，使东边的楚军得以发展壮大。张良早就想入关破秦，只是考虑到自己兵力不足，地盘有限，就是在韩地，虽然他攻破过不少城池，但常常是得而复失，所以至今仍没有一块稳固的根据地。如今老友刘邦率领大军来到韩地，他怎能不高兴呢？
“沛公今日准备如何用兵？”张良问。
刘邦想了想说：“先拿下开封，然后挥兵西进。”
张良说：“开封墙高池深，难以攻破。再说目前应以消灭秦军为主，不必把攻城略地放在心上。以我之见，可派少量军队，将开封包围，虚张声势，并不强攻。西部的秦军见开封被围，必来援救。我们事先将主力部署在开封西边，届时发起攻击，必能成功。”
刘邦听了觉得有理，欣然同意，便下令在开封四周扎下营寨，做出强攻的架势，而将主力部署在了白马（在今河南滑县东北）。
果然不出张良所料，秦将杨熊接到开封守军的告急后，立即率兵东进，当行至白马时，突遭袭击，只好向曲遇（今河南中牟县）仓皇逃窜。起义军紧追不舍，又在曲遇将秦军打得大败，杨熊只好率领残部退守荥阳。秦二世得知杨熊损兵折将，一气之下，派遣使者将他杀了。
这时，奉命北上救赵的次将项羽，斩杀了畏缩不前的主帅宋义，又破釜沉舟，打败了围困巨鹿的秦军。正当秦军势力骤减，刘邦入关指日可待之时，突然得到情报：赵国将军司马卬要南渡黄河，向关中挺进，夺取咸阳。刘邦闻讯，立即率军北上，抢先攻占阴平，控制了黄河渡口，断了司马卬先行入关的念头。
刘邦本想沿黄河一直西进，通过函谷关进入关中，不料在洛阳东一战中，惨遭失败。张良说：“函谷关是关中最重要的关塞，秦军的防守也最严密，不如向南迂回，通过辕关、武关和峣关进入关中。”
刘邦听了觉得有理，便放弃从洛阳、函谷关入关的打算。从近日一连串的战斗中，刘邦深深认识到，张良实在是个难得的谋士，便与张良商量说：“关中情况复杂，我又缺少帮手，你就和我一同入关吧！”
张良与刘邦本来就是老相识，如今通过几仗，对刘邦更增加了几分好感，听刘邦如此一说，正中下怀，欣然同意，于是将原有部队留给韩王成，继续在颍川一带转战，他自己告别了结婚不久的王氏，加入刘邦队伍中，成了刘邦的谋士。根据张良的建议，刘邦首先率军回攻阳城，夺得军马四千余匹和大批兵器，又在东大败南阳郡守吕。吕无奈，只好仓皇逃进宛城（今河南南阳），据险固守。
刘邦见宛城壁垒森严，一时难以攻破，若拖延下去，必会误了进关时机，于是率军绕过宛城，西行入关。约莫走了一个时辰，张良突然把刘邦叫住说：“关中秦军的力量还很雄厚，他们必会凭险固守，而宛城又会成为我们的一大后患。若舍弃宛城而西进，就形成前有劲敌、后有追兵的局面，前后夹击，我们可就危险了。”
刘邦一听，恍然大悟，立刻下令停止前进，询问张良有何打算。
张良说：“咱们不妨来个回兵之计。趁吕以为我军已经西进，杀他个回马枪，岂不很好！”于是刘邦下令全军趁着黑夜，从小路急行军，第二天天还没亮的时候，就把宛城一层又一层地团团围住了。
吕没想到刘邦会杀这个回马枪，束手无策，就想自杀。他部下有个叫陈恢的人劝解说：“将军这么匆忙地死去，未免太轻率了。秦皇暴虐无道，何必为他卖命。人们都说沛公宽厚，不如归顺他，既保百姓，也保自身。如果请降不成，再死也不为晚。”
吕听了陈恢的话，就让陈恢越墙出城，面见刘邦。陈恢对刘邦说道：“我听说楚怀王事先有约，谁先打进咸阳，谁就做关中王。将军为什么一定要攻占宛城呢？宛城是个大城，宛城治下还有数座县城，宛城的官吏、兵士和百姓都认为投降必死，所以宁愿拼死守城。将军若是一定要攻宛城，必然伤亡很大，那时攻城不下，旷日持久，不但不能抢先入关，而且背后还会受宛城守军的牵制。我为将军打算，不如接受宛城投降，使宛城官吏仍任原职，留守宛城，而把宛城的兵士编入您的队伍，同去西征。这样，其他各县见到宛城能够保全，官吏照常留用，也会开城迎接将军，将军就可以兵不血刃，直取咸阳。”在旁的张良点了点头，又给刘邦使了个眼色。刘邦会意，便对陈恢说：“依先生之言，这事就交给你办了！”
陈恢立即告辞回城。时间不长，只见城门大开，吕亲自出城，迎接刘邦。刘邦也以礼相待，封吕为殷侯，封陈恢为千户，让他们继续管理宛城事务。刘邦见宛城的局势稳定下来了，才又继续西征。
沿途的守城秦将，见吕献城之后，不仅保住了性命，而且受了封，于是纷纷效仿，不战而降，使刘邦很快就占领了丹水、胡阳、析、郦等地。
刘邦在西征途中注意结交豪杰义士、收买秦朝将吏，同时项羽又在河北消灭了秦军主力，造成关中空虚，所以在刘邦出兵西征的第二年八月，就以雷霆万钧之势，一举攻陷了武关，终于打开了关中南部的门户。