事实上，对于项梁的到来，有两个人比刘邦更为不安。他们就是刘邦名义上的两位领导——秦嘉与景驹。下邳属山寨楚国的势力范围，外来的军队随便驻扎成何体统，为了把这支军队从自己的地盘上赶走，秦嘉领兵来到彭城以东，威吓项梁。
秦嘉命令刘邦领兵前去接应。刘邦这次没有痛快前往，他要仔细算计算计，他可不想干折本的买卖。
经过仔细算计，刘邦认为项梁势大，绝对惹不起；秦嘉不自量力，后果堪忧。刘邦自忖自己的这点本钱，也就相当于个小地主，一旦下不准赌注，就会输个精光。刘邦决定两边都不得罪，一边好言应付秦嘉，一边派人去见项梁，表明自己的欢迎姿态。
项梁见秦嘉领兵向自己示威，决定趁机灭掉这小子，他召开军事会议动员说：“楚王陈胜首先起义反秦，作战不利，现不知去向。秦嘉背叛陈胜而拥立景驹，实属大逆不道！”
项梁出兵攻打秦嘉，秦嘉大败而逃。项梁领兵追击，一直到达胡陵城。胡陵城是秦嘉的老巢，他无处可退了，只得硬着头皮回师应战。当天，秦嘉战死，他的军队全部投降。景驹向北逃往梁地，死在那里。
刘邦到胡陵城去拜见项梁，只带了一百来名骑兵。由于早派人递上了好话，项梁对刘邦很友善。刘邦故伎重演，大倒苦水，请求拨付兵马进攻丰邑。项梁答应拨付给他五千兵卒，外带十名军官。刘邦大喜过望，自觉发了笔横财，现在他已有了一支一万四千人的部队了。
项梁之所以如此慷慨，是因为他打算西去找章邯会战，需要刘邦护卫自己的侧翼。就在不久前，项梁派朱鸡石带领一支军队对秦军做试探性进攻，大败而回。项梁一怒杀了朱鸡石，但这也让他明白，秦军的战斗力不容小觑，自己需要盟友的帮助。
刘邦决定先解决自己的问题。他再次领兵来到家乡，准备三打丰邑城。这次雍齿慌了，一来刘邦势大；二来他所效忠的魏国已经岌岌可危。雍齿明白继续坚守是愚蠢之举，他选择了逃跑。刘邦虽然痛恨雍齿，但也没有杀他的意思，没有穷追，任凭他逃到魏国躲了起来。
至此刘邦已渐成气候，成为一股不可忽视的抗秦力量。
公元前208年6月，刘邦有了两位领导。
事情大致这样，项梁灭掉景驹的山寨楚国不久，得到确凿消息：陈胜真的死了。这对项梁而言是件大事，他必须想出应对之策，避免出现危机局面。
说到这里，可能有人会感到困惑，陈胜与项梁有什么关系？他的生死，真的对项梁的这几万人马很重要吗？这件事情还需要从项梁起家说起。
先前，项梁叔侄避祸江东，隐姓埋名。但金子就是金子，到哪里都会发光。由于项梁才识过人，遇事能断，见义必为，所以他深受当地干部群众的尊重，成为了一个在当地很有影响力的人物，凡地方上兴办工程，或有红白之事，人们都喜欢请项梁帮忙。
项梁的侄子项羽也慢慢长大，这小伙子身长八尺，力能扛鼎，武艺绝伦，当地的青年人都拜服他。
陈胜在大泽乡对秦朝发难，东南地区受到震动，项梁想起兵响应，苦于手中掌握的资源有限，非常苦恼。正在这时，机会找上了门来。会稽郡守殷通早就听说项梁在民间很有影响力，他派人邀请项梁到府上做客，私下对项梁说：“目前，蕲陈失守，长江以西皆已反叛，这是老天要灭亡秦朝。我听说先发者制人，后发者为人所制，现在我想趁机起事，君意以为何如？”
项梁满心欢喜，极力表示赞成。殷通又说：“起兵须先择将，当今将才，莫如君与桓楚。”项梁说：“桓楚有罪在身，潜逃入大泽中，无人知其下落，唯侄儿项籍，与桓楚颇有往来，知其行踪。可使籍儿去召桓楚。”殷通大喜说：“很好，叫他来见我。”
项梁回到家中，与项羽定下一计。
然后，叔侄俩准备停当，一同前往郡衙。项梁吩咐项羽站在门口等待召见，自己入内去见郡守殷通。不多时，里面传话让项羽入内。项羽来到殷通座前，施礼参拜。不一会儿，项梁给项羽使了个眼色，说：
“可以行动了！”项羽迅速拔出佩剑，抢前一步，一剑砍下了殷通的脑袋。
项梁取得印绶，悬挂腰间，提起殷通的头颅，从容走出内室。衙门内的护卫见状大惊，各拽刀枪围拢上来，项羽举剑迎击，顷刻间杀了近百人。余众见项羽神勇，不敢继续抵抗，纷纷表示降顺。
叔侄俩控制了郡衙，召来社会各界的头面人物，宣布响应陈胜，起兵反秦。众人见事已至此，只得公推项梁担任郡守。项梁整顿本郡辖区内的兵马，又在社会上公开招了一部分，得到精兵八千人。
就在项梁叔侄用心经营江东之时，陈胜被章邯击败。这可急坏了一个人，这个人就是召平将军。召平被陈胜派来开辟后方根据地，在家乡广陵受阻，一事无成，现在陈胜败出陈县，想向东南方向退避，却没有自己的地盘。召平感到自己误事，很为内疚。他情急之下渡江来到江东，找到项梁，假借陈胜的名义拜项梁为“楚国上柱国将军”，命令他立即出兵，去解救楚王陈胜。
有了这样一个名分，项梁感到出兵的机会已经成熟，他与项羽立即带领八千子弟兵渡江西进。到达东阳县（在今江苏盱眙县境内）附近时，听说东阳县城已经被一个叫陈婴的人占领。陈婴拥兵两万，实力雄厚，项梁不敢小视，派使者前去谈判，希望与他联合西进，起码不要为敌。
陈婴这个人，曾是东阳县的县府办公室主任，居住在县城中，为人一向诚信谨慎，被称作长者。东阳县的年轻人杀掉了县令，相聚得两万人，准备拥立陈婴为王。陈婴的老母亲很有见识，对陈婴说：“自从我做了你们家的媳妇，还不曾听说你的祖先中有过地位显赫之人。而今突然获得大名声，不是什么好事；不如依附归属他人，这样，事情成功了，仍然得以封侯，事情失败了，也容易逃亡。”陈婴听从母亲的话，不敢称王。
陈婴见到项梁的使者，一番交谈后，决定投靠项梁，他对手下的军官们说：“项氏世世代代为将，在楚国享有盛名，如今想要办大事，将帅就非这种人不可。我们依靠名门望族，灭亡秦朝的事业必定能成功！”
他的部下听从他的话，开城迎接项梁。
项梁领兵渡过淮河，又碰上一件大喜事。有人报奏有一支人马来投，领头的将领有两位，一位姓英名布，另一名为蒲将军（这人是项羽帐下五大名将之一，可惜史书上没有记他的名，只记下他的姓，所以后世只能称他蒲将军）。这是一支劲旅，有几万人之众。
前文中说过，英布曾在骊山服役，后来逃出来，潜入长江中当了强盗。就这样一个贼人，现在何以发达，成了这支军队的首领？又因何前来投奔项梁？
原来，英布是个有理想、有抱负的强盗，陈胜起事后，他感到改变自己身份的时候到了，就去见番阳县县令吴芮，请求合作反秦。
吴芮这个人也不简单，他是徐福的朋友，楚国被灭后，他在偏远的少数民族地区收集游兵散勇，安定地方，得到了秦朝官方的认可。公元前207年，秦政府封他为番君，也就是少数民族地区的官长。后来他在靠近鄱阳湖的地方建立了一座城池，作为自己的官衙治所。
吴芮看到秦朝风雨飘摇，知道它很难长久；况且他对秦王朝也没什么好印象，所以就答应了英布的要求。吴芮是个极其谨慎之人，他怕英布反客为主，损害自己，索性把女儿嫁给他，与他结成至亲。
英布大喜过望，率领岳父交给他的数千军队，北上救援陈胜。到达陈县附近时，遇见了吕臣将军，才知道楚王陈胜已死。
这个吕臣曾是陈胜的贴身侍卫，陈胜被庄贾刺杀后，他又悲又愤，组建起一支青巾裹头的军队，号苍头军，发誓给陈胜报仇。他在新阳起兵，出其不意攻克了陈县，杀死庄贾，重新宣布以陈县为楚都，将陈胜葬在芒砀山，谥号为隐王。
章邯闻讯大怒，命令左右两名校尉夺回陈县。吕臣抵挡不住，弃城逃跑，正好遇见英布。两人合兵一处，反击追赶上来的秦军。秦军没有提防会突然冒出一支生力军，被打得大败。吕臣、英布再次夺回陈县。
英布虽然一战成名，但他并不愉快，或者说他有些迷茫——陈胜死了，吕臣文化水平不高，能力有限，不像个干大事的人——英布自感留在陈县没有意思。恰在此时，他听说了项梁的事迹，决定前去投靠，半路遇见蒲将军，两人很谈得来，所以一同前往。
在项梁的近十万军队中，真正无条件效忠项氏者，主要是那八千江东兵；至于其他部队，无论是陈婴、英布、蒲将军，还是刘邦，都是冲着陈胜与楚国的名号而来，对他项梁的忠诚度有多高，他心中并无数。
因此，陈胜死亡的消息被确凿证实后，项梁必须解决下一步让大家“效忠谁”的问题，这个问题如果解决不好，有可能会使这个抗秦联盟解体。
事实上，项梁早在接纳英布时，就知道陈胜已经死了，他之所以迟迟没有召开高级军事会议，把这个问题摆在台面上，一是因为当时景驹的山寨楚国还存在；二是因为他的侄子项羽领兵攻打襄城，尚未回来。
项羽不在场，他担心自己控制不了局面。
直到6月，项羽屠灭襄城，胜利归来，他才决定在薛城召开高级将领会议，公开讨论这个问题，刘邦也应邀参加。
会议召开前夕，有个老头求见项梁。这老头是居鄛（今安徽巢湖市）人，名叫范增。老先生自认为胸有奇计，不愿在家安身养老，跑到军前想发挥余热。
他劝说项梁道：“陈胜的失败本来就是应当的。秦朝灭亡六国，楚国最没有罪过。且自从怀王到秦国后一去不返，楚国人怀念他直至今日。因此楚南公说：‘楚国即便是只剩下三户人家，灭亡秦国的也必定是楚国。’陈胜首先起事反秦，不拥立楚王的后裔而自立为王，他的势力不能长久。现在您在江东起兵，楚地蜂拥而起的将领都争相归附您，是因为您家世世代代为楚国的将领，他们相信您能够重新拥立楚王的后代，复兴楚国！”
项梁感觉他说得在理，就在民间找到了一个牧羊人——楚怀王的孙子熊心，计划拥立他为新楚怀王。
有了这层安排，薛城会议开得很圆满、很成功。大会决定，让新楚怀王到盱眙建立新都城，任命陈婴为上柱国，陪伴左右。项梁自号武信君，全权负责新楚国的军事工作。
项梁对自己的这一招很满意，这是他的权宜之计，他并不真把新楚王当回事儿，只不过把他当一个招牌，等条件成熟后，用不着了，就可以摘下来扔进垃圾桶。然而，这个新楚王虽然是牧羊人出身，却不是草包，他有想法，有主见，城府很深。
刘邦阅人无数，他见到新楚王后，认定他是个人物。
刘邦深知，项梁与熊心这样两个有主见的人凑在一起，短期内没什么，可时间长了，非出矛盾不可，搞不好就会有大问题。到时谁胜谁负，很难预料。
这让刘邦陷入了两难之境。如果看当前的实力，他必须无条件效忠项梁；如果论名分，楚王为最高国家元首，也必须效忠。如果与项梁走得过近，楚王将来一定猜忌；如果与楚王走得过近，可能很快就有杀身之祸。这两个领导，他一个也不能怠慢，都需小心应对。
功夫不负有心人。刘邦对这个问题反复研究，终于找到了一个解决办法，历史上没有记载这个办法的具体内容，但大致可以推测，应该是这样：公开场合他只知有项梁，不知有楚王；私底下却对楚王保持应有的尊重，让楚王相信自己对他怀有善意。
事实证明，刘邦这份心血没有白费，他后来从中获得了巨大的利益。
