高祖刘邦被推举为沛公后，派樊哙夏侯婴攻打附近的胡陵和方与两地，后来因为他母亲刘媪去世，不得不罢兵于丰邑治丧。在自己的管辖范围内出现了这么大的动静，有人造反了，秦朝的泗川郡肯定不会不管的。（秦始皇把全国分为三十六郡，这个泗川郡本为四川郡，管辖泗水流域，治所在今天的淮北市相山区）泗川郡的监守叫平的这个人就带兵包围了丰邑，两天之后，沛公军队出城迎战，大破平的军队。就是在这个时候，担任泗水卒史的周苛、周昌两兄弟（后都先后担任过三公之一的御史大夫之职）加入他们的团队。
沛公破了平的军队后，就让雍齿带兵驻守丰邑，自己带兵去打薛（今徐州或山东滕州一带），在此打败了泗川郡守叫壮的军队，这个壮就逃到了戚县（今山东微山县），在这个地方被沛公左司马曹无伤（就是鸿门宴情节中向项羽告密的那个）捉住后来又杀掉了。这样，对于暂时还不想扩大地盘的沛公来说，他就带兵回兵到亢父（今山东济宁），后来又到方与（今山东鱼台），整休军队。
前面已经说过，陈胜称王后，急于扩大自己的势力范围，派手下将士四处出击。沛公在方与休整军队之时，陈胜手下的一支军队正好打过来，这个领队的是原魏国人叫周市的。周市这个人可以算得上一个贤人了，当初陈胜让他去打原魏国的地盘，他很快就把魏地平定了，魏地的百姓要拥立他为魏王，他坚决拒绝了，并派使者五次到陈胜那里请求立合适人选为魏王，陈胜最后让宁陵君魏咎（原魏国公子）为魏王，而周市则担任了魏国的相国。这个时候，周市就是以魏国相国的身份来攻打丰沛的。
周市这个人也颇有谋略，他派人对驻守沛县丰邑的主将雍齿传话，意思就是你也知道我们军队的战绩了，你投降了就给你封侯，不投降我们一旦打下来了就要屠城了。雍齿这个人是沛县世家子弟，他与前面提到的那个刘邦“以兄事之”的王陵关系很好，他们都应该属于当地上流社会的人物了。由于身份地位的不同，他虽然很早就与刘邦有交往，但是内心还是很看不起刘邦。王陵也是这样，虽然刘邦“以兄事之”，但是他一开始心里也是很看轻刘邦的，所以当刘邦成为沛公的时候，王陵也拉了一队人马，聚集几千人，占据南阳，被封为穰侯，只是到后来刘邦还定三秦，准备出关击楚时，王陵才以兵投靠刘邦。
雍齿在这种情况下就要考虑了，到底抱哪条粗腿更安全呢？周市这边军队实力比刘邦要强大得多，而且一旦战败，城破屠城，自己的一家老小性命难保，刘季这小子到底能跳多久还未可知呢？在这种情况下，雍齿就反叛了刘邦，接受了魏相周市的招降，仍然驻守丰邑，只不过服务的老板变了。
沛公得知雍齿竟然叛变了自己，立马带兵攻打丰邑，但是雍齿也不是吃素的，战斗力不弱，沛公没能攻下，不得不暂回沛县。沛公很生气，他对雍齿一向比较看重，所以把丰邑这样防守重地交给他，他现在竟然率领丰邑的子弟在这么一个困难时期背叛自己。沛公因此生了一场病，但是他不能善罢甘休，于是他先去留县（今微山湖区内）投靠了秦嘉。这一年是公元前208年，陈胜已经去见秦始皇了。
秦嘉何许人也？他曾经是陈胜的部下，陈胜死后，他就在留县自立为大司马，并和东阳人宁君拥立楚国贵族景驹为假楚王（相当于代理楚王）。刘邦去留县投靠秦嘉的路上，遇到了“汉初三杰”之一的张良，张良字子房，本是战国时韩国的贵族，后来韩国被秦所灭，张良就一直想复国报仇。他曾经打造了一个一百二十斤的大铁锤，与一个大力士埋伏在秦始皇东巡所经途中的一个叫博浪沙（今河南原阳）的地方的道路边，等秦始皇车队到来之时，他和那个大力士抬起大铁锤就朝秦始皇的马车投掷过去，结果没有击中目标，而是击中了秦始皇侍从的马车，他因此遭到官方的缉捕，于是隐姓埋名，在下邳（今徐州邳州）躲藏起来。
张良隐居在下邳的时候行侠仗义，还跟因杀人而躲藏在此的项羽的叔父项伯交好。正是这层关系，后来鸿门宴上才有了项庄舞剑，项伯保护刘邦的这一出，这是后话，暂且不提。张良在下邳隐居了十年，他听说景驹为楚假王，就去投奔他，结果在半道上遇到了沛公。沛公率领几千人夺取了下邳西部的土地，张良于是跟随了沛公并被拜为厩将（负责后勤方面的）。张良在隐居下邳时，曾得到一位神人所授的《太公兵法》，后来他日夜研习，兵法了熟于心。张良也多次用《太公兵法》来为沛公出谋划策，沛公常常采用他的谋略，对他很是赏识。张良之前也跟别人讲过兵法，别人都不认可和采纳，跟沛公一说，沛公就心有戚戚焉，张良也很佩服沛公，说：“沛公殆天授”。所以说要建立一个好的团队，有千里马，也要有识才的伯乐，高祖刘邦就是他们这个团队的伯乐，他能识才，所以他手下才有一个战斗力很强的千里马团队。
前面讲过，陈胜曾派周文带领一支军队直接攻打秦朝首都咸阳，结果遭到秦将章邯的追击，周文节节败退，一直退到渑池（河南三门峡），兵败自杀，章邯趁机收复了很多被义军占领的地盘。与此同时，秦朝派了一个司马叫尼的人，也带兵平定了楚地的很多地方，他先屠灭了相县（今安徽淮北西北），带兵来到了砀县（今河南永城芒山），与东阳人宁君和沛公所带的西进兵遭遇，沛公这方没有取胜，于是他们退到留县整编，继而又去攻打砀县，三天才攻下。沛公他们收编了砀县的五六千人，转而攻打下邑（今安徽砀山县），攻下来后带兵准备攻打丰邑。
沛公估计自己的人马还是不太够，听说项梁在薛县（今山东滕州市），就带了一百多名骑兵去见项梁。前面已经讲过，项梁叔侄杀了会稽守殷通起事，他是怎么到了薛县来的呢？这里要来说一说。原来陈胜手下有个叫召平的将领，他是广陵（今扬州）人，陈胜让他攻打广陵，结果没有打下来，后来他听说陈胜被杀，章邯大军也要打过来了，于是他率军渡过长江，假传陈胜的命令，任命项梁为上柱国，并建议项梁赶紧攻打秦军。项梁于是渡过长江向西进发，他听说陈婴已经打下了东阳（今浙江东阳），就派使者表达了想与他联军的愿望。
陈婴原来是东阳令史，令史是个很低级的职位，但是这个人很忠信谨慎，在当地口碑很好。陈胜起义后，东阳少年杀了他们的县令，聚集了几千人，来响应起义。但是在谁做首领呢，一时没有合适的人选，大家后来就想到了这个陈婴。陈婴就推辞说自己能力不够，那些年轻人就强行的让他当首领，陈婴没办法答应了，后来这个队伍竟然增加到两万人，那些年轻人又想让陈婴就地称王。他的母亲非常贤德，就劝陈婴说，你家祖上没有显贵的人，现在突然获此大名，恐怕不详，不如推给别人，事成犹可封侯，事败也容易脱身。陈婴听从了他母亲的话，不敢称王。
再说项梁派人来游说陈婴联兵，陈婴马上就答应了，并且动员手下的将官说，项氏是世家名门，我们依靠他们，才可以做大事，才可以灭秦。他手下人也觉得很有道理，都同意把军队归属于项梁统领。项梁收编了陈婴军队后，率兵渡过淮河，这时候，黥布（又叫英布，后归顺刘邦）、蒲将军（人名）也率军归顺，一时军队有六七万人，驻军在下邳。
这时，秦嘉已经立景驹为楚王，驻军于彭城（今徐州）东面。本来秦嘉与项梁的立场是一致的，都要反秦，但是这时候秦嘉看到项梁的进攻势头很猛，就想阻挡项梁的军队。项梁借口秦嘉背叛陈胜，擅立景驹为楚王，进兵攻打秦嘉。秦嘉战败逃至胡陵（今沛县），战死，景驹也逃跑了，这样项梁就收编了秦嘉的军队，驻军胡陵。本来正准备要向西进，后来得知章邯的军队已打到了栗县（今河南夏邑），项梁派副将朱鸡石（符离人，与秦嘉同举事，秦嘉败后投奔项梁）、余樊君带兵与章邯交战，余樊君战死，朱鸡石战败逃到胡陵。在这种情况下，项梁率军进入薛县，并且杀了朱鸡石（可能认为他没有死战，临阵逃脱）。。
再说沛公来见项梁，表达了与他联军反秦的愿望，项梁还不错，拨了五千士兵、五大夫级别（秦、汉二十等爵的第九级，级别不低）的将领十人交给沛公，沛公回来后，就带兵攻打丰邑。
当然丰邑的雍齿再怎么厉害，还是被打败了，他后来逃到赵地，再降刘邦。刘邦虽然很痛恨他在困难时期背叛他，但是不但没有杀他，反而还封他为什邡侯，食邑二千五百户，在功臣中位居五十七，这是后话。这也反映了沛公刘邦的宽容大度的一面，绝对不是那种睚眦必报的“无赖”（有人认为刘邦就是一无赖）所能做到的。