Lúc ban đầu Sở Hoài Vương từng giao kết với các tướng nghĩa quân: "Ai vào Quan Trung trước thì làm Vương". Nhưng nhiệm vụ tiến về phía tây để vào Quan Trung thì Sở Hoài Vương không giao cho Hạng Võ, mà giao cho Lưu Bang, là người có phong độ của một vị tướng lãnh chững chạc. Đó là điều may mắn cho Lưu Bang. Cho dù binh lực của ông quá ít, việc tiến quân tương đối chậm, nhưng so với Hạng Võ thì thuận lợi hơn nhiều. Lúc ban đầu, Lưu Bang nhận mệnh lệnh thu gom các binh sĩ tản lạc của Trần Thắng, Hạng Lương, khoảng chừng một vạn người, cùng xuất phát vào tháng 10 năm 207 Tr. CN tại quận Đảng, đánh chiếm được Thành Võ. Đến tháng 12 thì tiến quân tới Lật Ấp, giữa đường gặp Cương Hầu nhà Tần, thừa lúc tướng này không phòng bị bất ngờ phát động tấn công, thôn tính bốn nghìn quân của ông ta. Tiếp đó, lại gặp đại tướng của nước Ngụy là Hoàng Hân, Vũ Mãn cùng đem quân gia nhập rồi đánh bại quân Tần.
Vào tháng 2, Lưu Bang tiến đánh Xương Ấp nằm ở phía bắc, tại đây ông đã tiếp thu một đội ngũ do Bành Việt chỉ huy, nên lực lượng càng thêm mạnh. Bành Việt là người Xương Ấp, tự Trọng, làm nghề đánh cá, sinh sống tại Đại Trạch thuộc Cự Giả. Mặc dù nghèo, ông vẫn là người ngay thẳng, dám nghĩ dám làm, rất có uy tín với bá tánh tại địa phương. Sau khi tin tức Trần Thắng, Hạng Lương khởi nghĩa truyền tới Xương Ấp,, thì có một nhóm thanh niên trẻ tuổi tìm đến gặp Bành Việt, nói với ông:
- Thiên hạ hiện nay đang đại loạn, rất nhiều hào kiệt lần lượt đứng lên xưng vương, khởi binh chống Tần, vậy chúng ta cũng nên bắt chước họ, cùng đứng lên khởi nghĩa được không?
Bành Việt đáp:
- Hiện nay hai con rồng đang chiến đấu với nhau, bên nào cũng tài ba cả, vậy nên chờ đợi một thời gian.
Sau một năm, số thanh niên tại địa phương gồm hơn một trăm người, lại đến ra mắt Bành Việt, nhờ ông lãnh đạo cho họ khởi nghĩa. Bành Việt không chịu. Nhưng đến nhóm thanh niên thứ ba đến yêu cầu thì ông không từ chối được nữa, nên phải bằng lòng. Ông giao ước với hơn một trăm người đó, là sáng sớm ngày mai khi mặt trời vừa mọc thì phải tập hợp, ai tới muộn sẽ dựa theo quân pháp mà xử chém. Qua ngày hôm sau, khi mặt trời mới lên mọi người lần lượt kéo tới, nhưng có mười mấy người đến muộn, và người đến muộn nhất là đã giữa trưa. Bành Việt ngỏ ý đáng tiếc, nói:
- Tuổi tôi đã già thế mà các vị kiên quyết bầu tôi lên làm thủ lãnh, vậy tôi đành phải tuân mệnh. Tôi đã có lời giao kết về thời gian tập hợp, thế nhưng có rất nhiều người đến muộn, vậy làm thế nào đánh giặc được? Trong quân ngũ thì không có hí ngôn (nói đùa0 cho nên tôi đành phải chém người đến muộn sau cùng!
Nót dứt lời bèn xuống lệnh hành hình. Mọi người cười rộ nói:
- Tại sao lại làm thực? Về sau không chấp hành cái lệ đó cũng được mà!
Bành Việt nghiêm sắc mặt, nói:
- Trong quân ngũ không thể nể tình được, vậy cứ dựa vào quân pháp chém đầu.
Bành Việt cho mang người đó ra chém xong, thì dựng đài để làm lễ tế cờ, tuyên bố khởi nghĩa. Đến chừng đó mọi người mới hết hồn. Đối với Bành Việt tỏ ra sợ hãi, không còn dám ăn nói và hành động bừa bãi nữa. Sau khi Bành Việt chém một binh sĩ vô kỷ luật để khởi nghĩa, thì bắt đầu đánh thành chiếm đất, thu nạp những binh sĩ tản lạc của các chư hầu, lên đến hơn một nghìn người. Khi Lưu Bang tới Xương Ấp, Bành Việt nghe tiếng ông là người hiền đức nên dẫn quân tới xin gia nhập, đồng thời, giúp ông tấn công Xương Ấp. Thành Xương Ấp kiên cố khó đánh chiếm, nên Lưu Bang đành phải bỏ rơi, tiếp tục đi về phía tây, chỉ để Bành Việt ở lại tại đó.
Lưu Bang dẫn quân đi ngang qua Cao Dương. Trong ấp này có một người tên Lệ Thực Kỳ, gia cảnh bần hàn, thường làm nghề giữ cửa ở ngoài phố chợ. Trong phường có người làm lính kỵ binh của Lưu Bang, Lệ Thực Kỳ bèn nói với người lính này:
- Các tướng lãnh chư hầu đi ngang qua Cao Dương không dưới mấy chục người. Tôi nói chuyện với họ, thấy thái độ của họ tỏ ra rất dè dặt, tâm địa lại hẹp hòi, chỉ biết giữ những lễ tiết vụn vặt, thế mà người nào người nấy đều lên mặt cho rằng mình có tài cao hơn người một bậc, và không bao giờ họ nghe lọt vào tai những lời nói có tính chất bao dung rộng lượng cả. Nay nghe nói Bái Công mặc dù ngạo mạn, nhưng lại giản dị dễ gần, nhiều mưu lược, đúng là người mà tôi muốn đi theo. Chỉ đáng tiếc là không có ai giới thiệu tôi. Vậy nhà ngươi nếu gặp ông ta, thì nói nhà ngươi có một người đồng hương tên Lệ Mỗ năm nay ngoài sáu mươi tuổi, thân cao tám xích, mọi người đều gọi là Cuồng Sinh, nhưng riêng một mình ông ta thì lại không cho mình là Cuồng!
Người kỵ binh đó cười đáp:
- Bái Công không thích nho sinh. Có lần, một người nọ đội mão nho sinh vào ra mắt, Bái Công đã lột chiếc mão của anh ta xuống rồi tiểu vào trong đó. Khi nói chuyện với người khác, ông thường to tiếng mắng nho sinh là đồ vô dụng. Vậy ông không thể lấy tư cách nho sinh để đi gặp Bái Công được!
Lệ Thực Kỳ đồng ý, thế là người kỵ binh này liền vào báo với Lưu Bang.
Sau khi Lưu Bang đến trọ tại trạm dịch Cao Dương, phái người đi triệu kiến Lệ Thực Kỳ. Lệ Thực Kỳ bước vào thấy Lưu Bang đang ngồi một cách ngạo nghễ để cho hai mỹ nữ rửa chân, không thèm chú ý đến sự xuất hiện của Lệ Thực Kỳ ngay đến chào hỏi cũng không. Lệ Thực Kỳ rất giận, hỏi:
- Ông dự định giúp vương triều nhà Tần đánh các chư hầu, hay là dự định giúp các chư hầu đánh vương triều nhà Tần?
Lưu Bang to tiếng mắng:
- Anh là một thằng hủ nho! Thiên hạ bị sự cai trị tàn bạo của nhà Tần làm khổ đã lâu rồi, ai ai cũng muốn lật đổ nó, tại sao anh lại hỏi những lời vô ích như vậy?
Lệ Thực Kỳ đáp:
- Nếu ông muốn tập kết nghĩa quân, diệt trừ vô đạo, thì không nên có thái độ như thế khi tiếp kiến một người lớn.
Lệ Thực Kỳ bèn nói về việc hợp tung liên hoành của các nước chư hầu thời Chiến Quốc trước kia cho Lưu Bang nghe, Lưu Bang chưa bao giờ được nghe chuyện này, nên lấy làm hứng thú, mời Lệ Thực Kỳ cùng ăn cơm với mình và hỏi sách lược tiến quân về phía tây. Lệ Thực Kỳ nói:
- Binh sĩ mà túc hạ có trong tay chẳng qua là một đạo quân ô hợp, gồm những người dũng cảm ở khắp đó đây và những binh sĩ bị tản lạc chưa đầy một vạn người, vậy muốn đánh quân Tần đang ở thế mạnh, thì khác nào vuốt râu cọp. Theo tôi nếu túc hạ muốn tranh thiên hạ thì trước tiên phải lo cho tướng sĩ ăn no, Trần Lưu là một địa điểm quan trọng, có đường giao thông đi khắp các nơi. Trong thành chứa rất nhiều lương thảo, tôi lại là người bạn thân của viên Huyện lệnh. Nếu ngài bằng lòng tôi có thể giúp ngài dụ hàng ông ta. Nếu ông ta không chịu hàng, thì túc hạ cứ dẫn binh mở cuộc tấn công, còn tôi sẽ làm nội ứng. Lấy được Trần Lưu, túc hạ sẽ được cái lợi rất lớn.
Lưu Bang xuất thân hèn kém, quen tánh thô lỗ theo kiểu người phố chợ. Ông ta vừa ham tiền tài lại ham sắc đẹp. Việc mắng chửi thuộc hạ dưới tay là chuyện cơm bữa, nhưng mặt khác, ông lại thích tiếp nhận những lời nói thẳng, giỏi sử dụng nhân tài. Hai mặt cá tính đó của Lưu Bang đã hình thành một sự đối lập thống nhất trong con người ông. Nay nghe Lệ Thực Kỳ hiến kế, thấy rất có lý, nên tỏ ra rất kính trọng ông ta. Sau đó, Lưu Bang phái Lệ Thực Kỳ đi trước đến Trần Lưu, còn mình thì dẫn quân đi theo sau. Thế là Trần Lưu đã nhanh chóng quy hàng. Lưu Bang lấy rất nhiều lương thảo ở trong thành để bổ sung hậu cần đầy đủ. Lưu Bang thấy Lệ Thực Kỳ có công, nên phong cho ông làm Quảng Dã Quân. Người em trai của Lệ Thực Kỳ là Lệ Thương cũng dẫn bốn nghìn nghĩa quân tới gia nhập vào quân Lưu Bang, được Lưu Bang phong làm đại tướng, chỉ huy số quân giữ thành Trần Lưu.
Sau khi Lưu Bang chiếm được Trần Lưu, một địa phương chiến lược, thì cũng là lúc quân của Hạng Võ giải vây xong Cự Lộc, tiếng tăm lẩy lừng trong khắp các chư hầu. Tin tức đó cũng làm cho Lưu Bang hết sức kinh hoàng. Lời hứa "Ai vào Quan Trung trước sẽ là Vương" của Sở Hoài Vương vẫn còn văng vẳng bên tai. Ông ta sợ Hạng Võ sau khi chiến thắng Chương Hàm sẽ xua quân tiến về phía tây và vào Quan Trung trước, nên không dám chần chờ, lại tiếp tục tiến nhanh.
Tháng 3, Lưu Bang từ Trần Lưu tiến đánh lên phía bắc. Do quân Tần cố thủ chặt chẽ không thể đánh chiếm được, buộc ông phải chuyển sang hướng tây rồi đánh nhau một trận lớn với tướng Tần là Dương Hùng tại Bạch Mã, sau đó lại giao chiến tại Khúc Ngộ, đánh bại quân Tần. Dương Hùng sau khi bại trận bỏ chạy về Huỳnh Dương. Tháng 4, Lưu Bang tấn công quận Dĩnh Xuyên tại phía nam. Sau khi chiếm được thành này, ông lại được Hàn Vương Thành và Trương Lương giúp đỡ bình định nước Hàn. Lúc bấy giờ tướng Triệu là Tư Mã Ngang đang muốn vượt sông Hoàng Hà để vào Hàm Cốc Quan. Lưu Bang liền đánh chiếm Bình Âm ở phía bắc, cắt đứt con đường vượt qua sông của quân Triệu, để ngăn chặn họ phát triển về phía Hà Nam. Tiếp đó, Lưu Bang chuyển sang Lạc Dương, giao tranh với quân Tần tại phía đông Lạc Dương. Gặp bất lợi trong trận đánh này, Lưu Bang buộc phải đi theo đường Hoàn Viên là một con đường nhiều trắc trở để đi đến Dương Thành, rồi chuyển hướng sang quận Nam Dương và gặp Trương Lương dẫn binh tới gia nhập. Trong giai đoạn này, Lưu Bang mặc dù gặp phải một số thành ấp hậu phương của nhà Tầ phòng thủ kiên cố, chín lần bị trắc trở, ông trước sau vẫn được sự chi viện của Bành Việt, Lệ Thực Kỳ, Lệ Thương, Trương Lương. Ngoài ra còn thu được rất nhiều lương thảo tại Trần Lưu. Sở dĩ có được những thu hoạch lớn lao đó, là do Lưu Bang giỏi lôi kéo nhân tài và được dũng tướng cùng mưu thần giúp đỡ. Việc đó có tác dụng quan trọng đến sự phát triển sau này của Lưu Bang.
Tháng 6, Lưu Bang và Trương Lương dẫn quân tiến xuống phía nam, cùng giao tranh với Quận thú Nam Dương là Lữ Ỷ, đánh bại quân Tần, tiến lên chiếm hết cả quận Nam Dương.
Quận thú Nam Dương bị bại trận lui về thủ Uyển Thành, rồi dựa vào ngôi thành chắc chắn để tử thủ. Lưu Bang thấy Uyển Thành khó tấn công, nên kéo quân về phía tây. Trương Lương can rằng:
- Mặc dù ngài nóng lòng muốn tiến vào quan ải trước, nhưng quân Tần còn rất đông, nay nếu không đánh chiếm Uyển Thành trước mà tiến về phía tây, nếu bị quân ở Uyển Thành truy kích từ sau lưng, thì quân ta sẽ bị đánh cả hai mặt, rất bất lợi.
Lưu Bang nghe theo lời khuyên đó. Vào một đêm khuya ông dẫn quân theo một con đường khác, đổi cờ xí, đến sáng sớm thì quay lại bao vây ba lớp Uyển Thành. Quận thú Nam Dương là Lữ Ỷ thấy thế tuốt gươm ra định tự sát, nhưng một xá nhân của ông ta là Trần Khôi ngăn lại, bằng lòng thay mặt ông ta ra ngoài gặp Lưu Bang, yêu cầu Lưu Bang đừng mở cuộc tấn công vào thành. Thế là Trần Khôi trèo tường đi ra ngoài, đến gặp Lưu Bang nói:
- Thần nghe nói túc hạ có giao ước cùng chư hầu, ai vào Hàm Dương trước thì sẽ làm Vương. Nay túc hạ không đi về hướng tây mà lại mở cuộc tấn công Uyển Thành. Như vậy, người Uyển Thành sẽ dựa vào lương thực dồi dào, liều chết cố thủ. Cuộc tấn công nếu kéo dài sẽ bị tử thương không ít, vậy nếu không tấn công mà rời đi, thì lại sợ quân Uyển Thành từ sau lưng truy kích túc hạ. Túc hạ sẽ gặp cảnh phía trước bị chận, phía sau có quân đuổi theo, sẽ làm chậm trễ việc tiến về phía tây, mất đi cơ hội vào Hàm Dương trước. Cho nên thần thấy chi bằng túc hạ thuyết phục Uyển Thành đầu hàng, rồi phong Quận thú cũ làm quan, để cho ông ta giữ Uyển Thành cho túc hạ. Như vậy ông ta sẽ mở cửa thành đón túc hạ vào, giúp túc hạ kéo quân vào Quan ải một cách dễ dàng, không còn gặp trở lực gì nữa.
Lời nói của Trần Khôi được Lưu Bang tán thành. Qua đó khỏi cần hao tổn một tên lính nào mà lại chiếm được cả ngôi thành không phải tốt hay sao? Ông vui mừng tiếp nhận sự đầu hàng của Uyển Thành, và phong cho Lữ Ỷ làm Thân Hầu, vẫn tiếp tục làm Quận thú Nam Dương, lại phong Trần Khôi làm Thiên Hộ. Sau đó Lưu Bang dẫn quân tiến về phía tây, quả nhiên tất cả các thành ông đều đánh chiếm được. Khi tới Đơn Thủy, có Cáo Võ Hầu Tai, Tương Hầu Vương Lăng đến qui thuận. Lưu Bang lại kéo quân tới Hồ Dương, thì gặp Mai Quyên, một biệt tướng của Ngô Phiên Quân kéo quân tới gia nhập, rồi cùng đánh Tích và Lệ, cả hai vùng này đều đầu hàng. Thế là Lưu Bang lại tiếp tục xua quân tiến thẳng vào Võ Quan.
Tháng 8 năm 207 Tr. CN, Lưu Bang dẫn mấy vạn quân đến Võ Quan. Lúc bấy giờ tại chiến trường Hà Bắc, Hạng Võ đánh bại Vương Ly, và hàng phục được Chương Hàm. Đó là một thắng lợi to lớn. Trong vương triều nhà Tần đã xảy ra cuộc chính biến, Triệu Cao giết chết Tần Nhị Thế. Sau đó Triệu Cao phái sứ giả đến gặp Lưu Bang, muốn ký minh ước, chia vùng Quan Trung để cùng làm Vương. Lưu Bang cho rằng đó là cái kế xảo trá của Triệu Cao, nên không tin, xua quân định đánh chiếm Võ Quan. Tháng 9 cùng năm, Triệu Cao ra lệnh cho con trai của Phù Tô là Tử Anh trai giới năm hôm chuẩn bị đưa lên ngôi vua. Tử Anh liền bàn bạc với người con trai: "Triệu Cao đã giết Nhị Thế, nhưng hắn sợ quần thần sẽ đứng lên trừng trị hắn, nên giả vờ muốn đưa ta lên làm vua, đó là một cái bẫy của hắn. Nghe đâu Triệu Cao đã phái sứ giả đi gặp quân Sở, đôi bên hẹn nhau sau khi tiêu diệt nhà Tần thì họ sẽ chia đất xưng Vương tại vùng Quan Trung. Nếu giờ đây ta tắm gội, giữ mình trong sạch, đi triều bái Thái miếu thì nhất định hắn sẽ động thủ sát hại ta. Vậy chi bằng ta giả vờ bệnh không đi được. Hắn nhất định sẽ tới đây mời, chừng đó thì giết quách hắn đi." Triệu Cao quả nhiên sau mấy lần mời mà không thấy Tử Anh tới, bèn đích thân đến mời một lần nữa. Tử Anh giết Triệu Cao tại Trai cung, chu di cả ba họ của hắn. Sau đó, phái binh kéo tới Nghiêu Quan để tố chức phòng ngự, có ý đồ ngăn chặn bước tiến của Lưu Bang.
Nghiêu Quan là cổng phía nam Hàm Dương, là một nơi có vị trí hết sức quan trọng. Lưu Bang kéo quân tới trước Quan ải này thì cho quân hạ trại rồi dẫn người đi xem xét địa hình, chuẩn bị mở cuộc tấn công, Trương Lương biết được liền xin ra mắt Lưu Bang lên tiếng khuyên:
- Nghiêu Quan là địa hình hiểm trở, dễ thủ khó công, không thể hành động liều lĩnh. Thần nghe nói iên tướng giữ Nghiêu Quan là con trai của Đồ Hộ, một người làm nghê buôn bán tham lam, tham những quyền lợi nhỏ nhặt. Như vậy đối với người này chúng ta không cần phải dụng binh, mà dùng tiền để mu chuộc là được.
Lưu Bang cho là phải, hỏi Trương Lương làm cách nào, Trương Lương đáp:
- Ngài cho toàn quân xây hào đắp luỹ kiên cố, giữ trận địa cho vững vàng để phòng địch tấn công bất ngờ. Đồng thời, chuẩn bị đủ lương thực cho năm vạn người ăn, rồi phái binh sĩ lên những đỉnh núi chung quanh cắm thật nhiều quân kỳ để làm nghi binh, sau đó phái Lệ Thực Kỳ là người giỏi ăn nói đem vàng đến tướng giữ ải để dẫn dụ ông ta đầu hàng.
Lưu Bang nghe theo kế của Trương Lương, nhất nhất đều làm đúng y như vậy. Người con trai của Đồ Hộ đang giữ ải Nghiêu Quan quả nhiên thấy lợi đã động lòng tham, phản lại vương triều nhà Tần, ngỏ ý bằng lòng gia nhập quân đội của Lưu Bang để đánh Hàm Dương. Lưu Bang rất vui mừng, vừa mới định đồng ý thì Trương Lương lại ngăn ông, nói:
- Giờ đây chỉ có một mình tướng giữ ải Nghiêu Quan chịu đầu hàng, còn binh sĩ dưới quyền ông ta thì chưa chắc theo ông ta, và nếu họ không theo thì rõ ràng là rất nguy hiểm. Vậy chi bằng thừa lúc chúng đang mất cảnh giác, ta mở cuộc tấn công bất ngờ thì Nghiêu Quan có lo gì không chiếm được.
Thế là Lưu Bang dẫn quân đi vòng qua Nghiêu Quan, vượt qua núi Quý Sơn để đánh vào phía sau lưng của quân Tần, đại phá được quân Tần ở phía nam Lam Điền, rồi lại kéo tới Lam Điền. Sau đó họ lại mở trận chiến đấu với quân Tần ở phía bắc Lam Điền và cũng giành được đại thắng.
Lam Điền còn cách Hàm Dương không bao xa, và không còn nơi bố trí phòng thủ của quân Tần. Thế là đại quân của Lưu Bang vênh mặt, ưỡn ngực kéo tới Bá Thượng nằm ở ngoại thành Hàm Dương, chuẩn bị mở cuộc tấn công cuối cùng vào đô thành của nhà Tần.
Tin tức quân đội của Lưu Bang đã đến sát chân thành, làm cho Tử Anh vừa lên ngôi được bốn mươi sáu ngày hết sức hốt hoảng. Ông ta biết đại cuộc đã hỏng, bèn dẫn các quan viên trong triều đình ra đầu hàng Lưu Bang, đem ngọc tỷ (ấn vua) tượng trưng cho quyền lực của hoàng đế dâng lên trước mặt Lưu Bang. Vương triều nhà Tần cượng thịnh trong nhất thời, đến đây đã bị diệt vong. Thời điểm đó là tháng 10 năm 206 Tr. CN.
Lưu Bang khi mới khởi nghĩa, trong tay quân đội không đầy một vạn người, lực lượng rất yếu. Sở Hoài Vương phái ông ta đi chiếm đất ở phía tây, vốn muốn ông ta kềm chế quân Tần gây rối ở hậu phương. Đó chính là nhờ những biến cố trong nội bộ của vương triều nhà Tần đã tạo cơ hội cho ông. Việc phòng ngự bên ngoài của vương triều nhà Tần bị buông lỏng đã tạo điều kiện tốt cho ông. Riêng việc Hạng Võ đánh bại quân Tần do Chương Hàm chỉ huy cũng khiến binh lực của vương triều nhà Tần cơ bản đã lung lay, giúp cho Lưu Bang trên đường tiến về phía tây gặp nhiều thuận lợi. Hai bậc anh hùng cùng một lúc xuất chinh, một người gặp nhiều gian truân, trắc trở, người kia thì toạ hưởng sự thành công của đối phương. Chẳng những thế, Lưu Bang còn nhờ vào việc lôi kéo nhân tài, nên trên đường tiến về phía tây đã mở rộng được lãnh thổ, tăng cường được lực lượng của mình.
Đó là cái may mắn của Lưu Bang. Nhưng đối với Hạng Võ thì đó lại là một sự uy hiếp tiềm tàng.