（韩信）抱王霸之大略，蓄英雄之壮图，志吞六合，气盖万夫。
——（宋）苏轼
（一）
秦二世元年九月，项羽叔侄两人在江东响应陈胜、吴广，杀会稽太守殷通，聚众数千人，起兵反秦。项梁自任会稽太守兼大将军，部署吴中豪杰担任校尉、军侯、司马等，又任命项羽为裨将。
就在这时，广陵（今江苏省扬州市）人召平来到江东。陈胜、吴广的起义军壮大后，召平被封为将军，受命攻打广陵。然而广陵兵强城坚，久攻不下。与此同时，陈胜的大军在荥阳（今河南省荥阳市）也遭遇到少府章邯率领的秦军主力，惨遭失败。
起义受挫后，各地起义军之间及其内部的矛盾也逐渐暴露出来。原先赵、齐等六国的旧贵族纷纷自立为王，而陈胜自己也忘记了“苟富贵，勿相忘”的誓言，逐渐脱离普通士卒。
不久，吴广被同为起义军将领的田臧矫传陈王之诏杀死。召平听说陈胜败逃，秦兵又步步紧逼，便果断渡过长江，矫传陈胜命令，封项梁为楚王上柱国。
召平对项梁说：
“陈王让在下转告将军，江东已经安定，可速速发兵西进，攻打暴秦。”
项梁大声道：
“我等正有此意！”
召平感激不尽地说：
“诛暴秦、平天下就全凭将军之力了。”
第二天，项梁叔侄便带着8000名江东子弟渡江西去，准备攻打秦军。这时，陈婴所部已经攻下东阳（今江苏省宝应县）。项梁立即派人与其联络，希望合兵一处，一起西进攻秦。
陈婴原是东阳令史，为人诚信谨慎，深受百姓拥戴。大泽乡起义之后，东阳的年轻人便杀死县令，聚众反秦。这些年轻人想推选一个首领，但遍观阵中，竟没有一个能够服众的。于是，众人便请陈婴出山，强行立其为头领，聚众两万余人。
东阳起义军都用青巾裹头，自称苍头军，以区别于其他武装力量。苍头军众头目想立陈婴为王，但陈婴的母亲却对儿子说：
“自从我成为你陈家的媳妇以来，从未听说过你家祖先有过贵人。现在你突然得了大名，不是什么好事。不如找一个领头的，你作他的属下。如果成功了，你起码能得个万户侯；如果失败了，你也好逃亡。”
陈婴听从了母亲的建议，不敢称王。就在这时，项梁的使者到了，他对苍头军众头目说：
“项氏世代为将，在楚国颇有名望。现在要举大事，非要选这等人为将帅不可。我们依靠有大名的世族，一定可以消灭暴秦。”
于是众人听从陈婴的建议，悉数投靠了项梁。项梁叔侄两人实力大增，遂率部挺进淮河流域。
秦二世二年（公元前208年）初，项梁带领数万起义军渡过淮河。韩信听说这件事后，立即赶往淮河之滨，加入到起义军队伍中。当时，淮河以北地区的起义军有好几支，其中包括在沛县（今江苏省沛县）起兵的刘邦、彭城（今江苏省徐州市）的秦嘉等。
刘邦出生于秦昭襄王（秦始皇的曾祖父）五十一年（公元前256年，一说出生于秦庄襄王三年，即公元前247年）。他的父亲是沛县丰邑镇中阳里金刘寨村的一个普通农民，名字不详，人称刘太公。刘邦在家中排行老三，上面有两个哥哥。按伯、仲、季排序，老大叫刘伯，老二叫刘仲，老三叫刘季，即刘邦。刘邦这个名字应是他起兵反秦后或登基称帝后所用的名字。
刘邦自幼顽劣，不爱读书，也不愿意从事农业生产。早年，他与好友卢绾一起拜马维先生为师，在马公书院读书，但经常逃学，常被老师训斥。他的父亲刘太公也认为他胸无大志，经常骂他游手好闲，不务正业。
不过，刘邦性格豪爽，乐于结交朋友，又仗义疏财，手下聚拢了一帮小哥们儿，其中也包括樊哙和周勃等人。樊哙出身寒微，以屠狗为业，好狠斗勇，但很讲义气；周勃靠编织养蚕用的竹席为生，遇到有丧事时还兼给人家做吹鼓手。樊哙和周勃都很敬重刘邦，尊其为大哥。
成年后，刘邦“试为吏”，做了泗水亭长。泗水亭位于沛县县城东郊，是附近的大亭，又称都亭，因此这里亭长的职位自然也比一般的小亭长高些。
当上亭长后，刘邦很快就与县里的官吏们混熟了，在当地成为一个小有名气的人物。沛县功曹椽萧何、典狱椽曹参、狱吏任傲、县吏夏侯婴等人，也都成了他的好友。
（二）
刘邦担任了十多年的亭长，除交一帮朋友、娶了一个能干的妻子外，并没有什么建树。他的妻子是单父（今山东省单县）人吕公之女吕雉。因史书记载不详，现已无法得知吕公的出身和生平事迹了。从《史记·高祖本纪》的字里行间推测，吕公应是一个读过几天书的乡绅，善于相面。后因在家乡与人结下冤仇，吕公举家搬迁到沛县定居。
吕公与沛县县令是多年的好友，县令自然殷勤相待。县中之人听说吕公和县令关系密切，都纷纷登门拜访。一时间，县衙人满为患。于是，功曹椽萧何就想了一个拒客的办法。他宣布：凡是贺礼钱不到一千钱的人，一律到堂下就坐。
这种场合自然少不了刘邦。刘邦虽然不名一文，但却大大方方地在县衙前对看门人说：
“我出贺钱一万，快快前去通报。”
吕公闻言，立即亲自出来相迎。一见刘邦器宇轩昂，与众不同，吕公心里暗暗喜欢，便让他坐上座。萧何在一旁提醒吕公说：
“刘季平时最喜欢说大话，从没见他干成过什么大事。”
但吕公深信自己的眼光，不为所动，坚持将刘邦留下来。酒足饭饱后，吕公借着酒劲说：
“老朽善于相面，相人无数，但没有一个人能跟足下相比的，请足下一定要自爱啊！老朽有一个女儿，愿意许配给足下。”
刘邦一听吕公要将女儿许配给自己，心下大喜，当下就拜起了丈人。吕公的女儿吕雉是出名的美人，且知书达理。沛县县令多次向吕公提亲，吕公都没有答应。吕公的妻子吕媪听说吕公将女儿许给了刘邦，便生气地对吕公说：
“你经常说我们的女儿是个奇女子，要把她嫁给贵人。县令多次向你提亲，你都不答应，现在为什么要将她许给小小的亭长呢？”
吕公笑着说：
“这不是你们女人家能知道的事情。”
就这样，吕公将女儿吕雉嫁给了刘邦。吕雉就是中国历史上著名的吕后，与刘邦成亲后育有一儿一女，儿子刘盈，即后来的孝惠帝；女儿鲁元，即后来的鲁元公主。
在秦朝统治即将分崩离析之际，刘邦以泗水亭长的身份押送民夫前往骊山，为秦始皇修建陵墓。结果，刘邦一行才刚刚赶到芒砀山（今河南省永城市一带），民夫就逃了大半。刘邦心想，照这样发展下去，不等到骊山，民夫就全部跑光了。秦朝法律规定：民夫逃亡，亭长要承担连坐之罪。与其和民夫们一起到骊山去送死，倒不如放了大家。
想到这里，刘邦便准备了酒肉，和大家大吃大喝一顿，然后对众人说：
“你们都逃命去吧，我也要远走高飞了。”
众人闻言大喜，都纷纷散去，也有几十人不愿离去，想继续跟着刘邦。刘邦借着酒劲，带众人抄小路逃到山里，不觉就到了夜晚。突然，走在前面的人大叫道：
“前边有条大蛇挡在路上，还是回去吧。”
刘邦醉醺醺地说：
“大丈夫走夜路，有什么可怕的！”
说罢他冲上前去，拔剑就将盘踞在小路中央的大蛇斩为两段。众人高呼，又跟着刘邦向前走去。刘邦醉得厉害，走了几里路后就倒在路边呼呼大睡起来。
落在后面的人来到斩蛇的地方，忽然看见一位老妇在暗夜中哭泣。行人就问她：
“老妈妈为什么要在这里哭泣？”
老妇人回答说：
“有人杀了我的孩子，我在哭他。”
行人又问：
“你的孩子为什么被杀？”
老妇又说：
“我的孩子是白帝之子，变化成蛇，挡在道路中间，如今被赤帝之子杀了，我就是为这个哭啊。”
众人都以为老妇人在说谎，正要打她，老妇人却忽然不见了。
待后面的人赶上刘邦后，刘邦已经酒醒。那些人就把刚才看到的事告诉刘邦，刘邦心中暗暗高兴，同时也更加自负。而那些追随他的人也渐渐开始畏惧他了。
这个故事出自《史记·高祖本纪》。《高祖本纪》中夹杂着不少具有神话色彩的记载。这可能是刘邦当上皇帝之后，史官为了神话他而刻意编造出来的，纯属无稽之谈。而且其中还说，刘邦逃亡芒砀山之后，谁不知道他在什么位置，但吕雉却能轻而易举地找到他。刘邦就问妻子是怎么找到自己的。吕雉回答说：
“你所在的地方有祥云笼罩，我循着祥云就找到你了。”
这些当然都是传说。不过，刘邦和吕雉的确很聪明。他们利用民间的迷信思想，大肆宣扬刘邦的与众不同，招揽民众。当陈胜和吴广在大泽乡起义时，刘邦的手下已经聚拢了数百名亡命之徒了。
（三）
大泽乡起义后，秦朝各地的地方官举兵起事者也不在少数。沛县县令立即召集萧何、曹参等人，商议起事相关事宜。萧何等人说：
“你身为秦朝官吏，如果率众反秦的话，沛县子弟恐怕不会听从你的命令。不如将本县流亡在外的人召集回来，可以得数百人。大人手中的兵力增强了，自然没人敢不听你的号令了。”
县令觉得萧何等人说得有理，便让樊哙把刘邦找回来。刘邦带着数百人，跟着樊哙返回沛县。但等他们到达城门口时，却发现沛县城门紧闭，县令根本没有让他们入城的意思。
原来，县令担心自己无法控制刘邦，弄不好还会被刘邦所杀，等于引狼入室，因此命人将城门关闭，还准备诛杀萧何和曹参等人。
萧何等人闻讯大惊，立即潜到城外，悄悄与刘邦会合。刘邦向城内射了一封信，信中写道：
“天下百姓受秦王朝统治之苦太久了！沛县的父老虽然能帮助县令守住沛县，但却改变不了诸侯并起的局面。到时候，沛县遭屠，男女老幼都要遭殃啊！不如共诛县令，择沛县子弟中可立者立之，以应诸侯，保卫家室。”
平日里沛县百姓就对县令不满，再加上刘邦这样一煽动，众人立即杀了县令，开门迎进刘邦。就这样，刘邦被立为沛公，设祭坛，立赤旗，自称赤帝的儿子，领导民众举起了反秦大旗。到项梁渡淮之时，刘邦的部众已发展到两三千人，占据了今苏、鲁、豫、皖四省交界处的广大地区。
除刘邦之外，占据彭城一带的秦嘉实力也十分强劲。但目光敏锐的韩信毅然选择了项梁，其中主要的原因，大概是因为项梁、项羽都是很有魄力的军事指挥家，又出身楚国将门，本身对百姓就具有很强的号召力。韩信用他超凡的洞察力和智慧分析了当时各地义军的力量，坚定地认为只有项梁、项羽叔侄俩所领导的起义军才能成为反秦斗争的中流砥柱。他的这一判断无疑是十分正确的。
就在韩信仗剑从军的同一时间，在番阳（今江西省鄱阳县）起兵的英布和另外一支反秦起义军将领蒲将军也渡过淮河，赶来投靠项梁。如此一来，项梁叔侄的队伍瞬间就扩大到了六七万人，驻扎在下邳（今江苏省邳州市）。
此时，陈胜已在逃亡途中被他的车夫庄贾所杀，其部下也已四分五裂，各自为政了。驻扎在彭城东的秦嘉闻讯，立即拥立景驹为王，布阵抵挡项梁大军。项梁立即召集诸将，吩咐说：
“陈王首先起兵反秦，功莫大焉。如今陈王兵败，不知所踪，秦嘉却背叛陈王，立景驹为王，这是大逆不道啊！”
诸将闻言，无不义愤填膺，纷纷表示愿意率部攻伐秦嘉。此时的韩信还只是项梁麾下的一名普通士兵，没有率部冲锋陷阵的资格，而且现在也已无法知晓他是否参加了攻伐秦嘉的战役。在项梁大军的强大攻势下，秦嘉很快败下阵来，在乱军中被杀，景驹也在逃亡途中死掉了。
项梁收拢了秦嘉的败军，准备挥师西进。秦朝大将章邯也已击溃了陈胜的残部，率军抵达栗县（今河南省夏邑县）。项梁立即指挥大军迎敌，同时派项羽攻打襄城（今河南省襄城县）。项梁派去迎击章邯的大军作战失利，但项羽历经苦战之后拿下襄城，屠杀了全城男女老幼。
不久，项梁又召集各地起义军将领到薛（今山东省滕州市南）商议抗击秦军的计划。刘邦作为沛县起义军的首领，也参加了这次具有重要意义的军事会议。居巢（今安徽省芜湖市居巢区）人范增也不远千里地赶到薛地，向项梁献计献策。
范增虽然已年届70岁，但见识不凡。他对项梁说：
“陈胜之败是必然的。当时，秦灭六国，楚国是最无辜的。自从怀王（？-前296年，公元前328-前299年在位，被秦国扣留，死于秦国）客死秦国之后，楚人至今都怀念他，所以才有‘楚虽三户，亡秦必楚’的说法。陈胜起兵反秦，不立楚国王室之后为王，反而自立，自然无法长久。如今，将军在江东起兵，楚国故地之人争相依附将军，就是因为项氏世代为楚将啊！”
项梁认为范增说得很有道理，立即起身，向范增深鞠一躬，说道：
“请先生教我该怎么做？”
范增笑着说：
“将军何不去寻找怀王后人，立其为王呢？”
项梁恍然大悟，立即吩咐项羽带人去找楚怀王熊槐的孙子熊心。
原来，楚国灭亡后，熊心便隐姓埋名，在穷乡僻壤替人牧羊为生。项羽历经千辛万苦，终于将熊心带到彭城。诸将立即拥立熊心为楚怀王，建都盱台（今江苏省盱眙县），以顺应民意。陈婴被封为上柱国，食邑五县，与楚怀王留守都城。项梁自号武信君，指挥大军对抗秦军。
不久，项梁便指挥起义军在东阿（今山东省东阿县）大败秦军主力。项羽与刘邦也率部攻城略地，占领城阳（今山东市菏泽市牡丹区一带），迫使秦军龟缩在濮阳城（今河南省濮阳市）中不敢出战。