起义不久，刘邦攻杀泗川守壮，令雍齿守丰。秦二世二年（公元前208年）十二月，魏遣周市说雍齿降，雍齿叛归魏。刘邦引兵攻雍齿，不胜，欲借秦嘉兵，故率众从秦嘉。是时秦将章邯已屠相，至杨东，秦嘉率刘邦与秦军战于萧西，不利。二月，攻取砀，得兵六千，进而攻拔下邑。四月，项梁攻杀秦嘉，驻薛。刘邦率百余骑投奔，项梁益刘邦兵卒五千，五大夫将十人。刘邦还军攻丰，雍齿败，走魏。七月，章邯围田荣于东阿，刘邦从项梁救田荣，大破章邯军。八月，刘邦与项羽西至雍丘，大败秦军，杀三川守李由。九月，楚怀王拜刘邦为砀郡长，封武安侯。
二世三年（公元前207年），楚怀王遣将攻关中，并与诸将约：“先入定关中者王之。”项羽因怨恨秦杀项梁，积极请战，要求率兵攻关中。楚怀王嫌项羽標悍残暴，不准。别遣刘邦收陈胜、项梁散卒，西攻关中。刘邦自砀出发，于成阳、杠里两败秦军，至昌邑遇彭越，共攻秦军。战不利。还军栗，夺取楚怀王将刚武侯军，得四千余人，西走高阳。郦食其献策，说刘邦攻取陈留，得秦积粟。刘邦纳其言。遣其弟郦商攻开封，城坚不拔，乃西攻白马、曲遇，大破秦将杨熊。杨熊走荥阳。二世遣使斩之。
刘邦攻南阳，南阳守欹败走宛城。刘邦欲越宛城，直取关中。张良谦曰：“沛公虽欲急入关，秦兵尚众，距险。今不下宛，宛从后击，强秦在前，此危道也。”刘邦遂连夜引兵还，围攻宛城。宛守椅欲自杀，舍人陈恢逾城谏刘邦收降椅，否则以宛郡县城之坚，“足下尽日止攻，士死伤者必多。引兵去，宛必随足下后。足下前失咸阳之约，后又有强宛之患。为足下计，莫者约降，封其守，因使止守，引其甲卒与之西。诸城未下者闻声争并门而待，足下通行无所累。”崎降，封为殷侯。陈恢献策有功，封千户。于是刘邦引兵而西，“无不下者”。刘邦遭魏人宁昌使秦，未还，章邯已降项羽。赵高杀二世，遣使于刘邦，欲约分关中，刘邦不许。秦子婴杀赵高后，遣将守峣关。刘邦遣郦食其、陆贾说秦守将以利害。秦将欲从，刘邦乘其懈怠，绕峣关，逾蒉山，大破秦军于蓝田南，又破秦军于蓝田北，秦军彻底瓦解。汉元年（公元前206年）十月，刘邦至霸上，秦王子婴降于秩道旁。秦亡。刘邦进入咸阳。
刘邦进入咸阳以后，接受樊哙、张良的劝告，把秦朝府库封存起来，还军霸上。萧何于是尽收秦丞相御史府律令图书。
秦制，丞相佐助天子，处理国家大事。御史大夫相当于副丞相，对外监督各郡御史，对内接受公卿奏事，按章举劾。除军权外，丞相、御史大夫几乎总揽一切朝政。御史大夫的属官御史中丞掌管图籍秘书。萧何为吏多年，他当然知道这是个要害部门。刘邦入咸阳时，诸将多争抢金帛财物，萧何却抢先进入秦丞相御史府，把律令图书收藏起来，使刘邦对于天下的关塞险要、户口多寡、强弱形势、风俗民情等等都能了若指掌。后来，在楚汉相争中刘邦能料敌制胜，这是一个非常重要的有利条件。当时入关诸侯，项羽拥兵四十万，号称百万，刘邦十万，号称二十万，强弱之势明若观火，而老谋深算的萧何，这时已经在为下一步刘邦与项羽争夺天下作了准备。
按照当初和项羽的约定，谁先入咸阳即为王，这样刘邦按理应称王。然而自恃兵多将广的项羽根本不把先前的约定当回事，他屡次以武力威胁刘邦退出咸阳，由他称王，并设鸿门宴欲除去刘邦，除掉这一心头之患。在这种危急的形势下，张良、萧何认真地分析了当时两军的实力，认为不可与项羽发生正面冲突，以免发生不幸。当务之急是先保存实力，日后待时机成熟后再与项羽争一高下。
刘邦表面上对项羽言听计从，使项羽消除了杀害刘邦的念头，他只想封刘邦到外地去，离开关中。项羽的丞相范增得知后对项羽说：“你不杀刘邦，实在是一大错误。今天又要加害他，这样更是留下遗患了。
项羽说：“他未尝有罪，无故杀他，必致人心不服。”范增见无法说服项羽，只好说：“既然如此，不如加封他为蜀王，蜀地甚险，易人难出。再封秦之降将章邯、司马欣、董臀三人分王关中，阻住蜀道，以阻刘邦。”
项羽非常满意，于是便封刘邦为蜀王。
刘邦得知后非常愤怒：“项羽无礼，竟敢背约，我愿与他决一死战。”樊哙、周勃等人也都磨掌擦拳，想去厮杀。唯独萧何进谏道：“此计万万不可，蜀地虽险，总可求生，不至速死。”
刘邦说：“难道去攻项羽，便至速死吗？”
萧何说：“敌众我寡，百战百败，怎能不死？汤武臣服于，无非因时机未至，不得不委屈求全。今诚能先据蜀地，爱民礼贤，养精蓄锐，然后还定三秦，进图天下，也未为迟。”
刘邦听了，怒气稍减，转而问张良。张良也同意萧何的说法，只是提议贿赂项伯，使他转达项羽，求其分封汉中地，因为汉中离关中较近，日后好作打算。
项羽十分爽快地改封刘邦为汉王，令其火速离开中，赴汉中为王。刘邦当了汉王，即请萧何为相。
正在这时，张良却因家中有事要暂时离别。临别前，刘邦、萧何、张良等人眼含热泪，依依不舍。
张良拉着刘邦和萧何的手说：“你们没感到日后要想统一天下，军营中还缺少什么？”
刘邦沉思片刻摇摇头：“军营之中不缺什么，文有你及萧何，武有曹参、樊哙和周勃，粮草马匹兵器样样都有。”
张良恳切地向刘邦建议要招一位文武全才的大将军：“我虽能出谋刘策，可手无缚鸡之力不会带兵，萧何克有政务之才，也不会带兵，曹参、樊哙虽勇猛过人，但只是一介武夫，很难统领百万兵将，况且也无人能敌过项羽，大王日后如何与项羽争夺天下？大王要想夺取天下，身旁非得有一名文武全才之人佐助，方能统兵与楚争雄，以至日后统一天下。”
“言之有理！”萧何听罢点头称是。
张良紧握住萧何的手：“望萧兄好好辅助大王，日后军中急需文纳贤士，如能觅得一二栋梁之才，便兴汉灭楚有望了。”
萧何说：“贤弟放心！我一定尽自己全力，为大王招贤纳士，振兴汉军。”
张良走后，出谋划策的重担落到萧何一人身上，他再次向刘邦分析形势，劝刘邦快速奔赴汉中：“臣已查明，汉中乃是块盆地，北瞰关中，南蔽巴蜀，东抵襄邓，西控秦陇，此地正好屯兵养马，积草囤粮，养精蓄锐，日后好重返关中，以成大业。”
刘邦听从了萧何的计策，率兵从褒斜道进入汉中，并烧了栈道。这样既可防备诸侯出其不意的袭击，又可表示绝无东归之意，使项羽更加对刘邦不提防。
刘邦兵抵南郑，休兵养士，操练部队。萧何向刘邦建议可以一边操练人马，一边开仓放粮，赚救饥民。于是偏远的南郑城镇时热闹起来，车水马龙，人来人往，一派繁华景象。
