可是，谁想到还没等官兵腾出手来，刘邦他们自己就不请自来了。芒砀山在永城东边，刘邦他们选择从西边城门攻城。由于守城的官兵没有任何防备，趁晚上城门还没关的时候，就先由小分队把守门的官兵制服了，随即大部队跟着蜂拥而入。在攻城之前，他们就已经把永城内的情况了解得清清楚楚了，三支队伍一支攻打府衙，一支占领各个城门，一支攻打兵营。就这样，刘邦的队伍以迅雷不及掩耳之势占领了整个永城，官府还没等弄清怎么回事，就被起义军给端了老窝，太守也被活捉了。大批秦军措手不及，还没等拿上武器，就被起义军杀死了。整个战斗干脆利索，刘邦稍后清点义军，只有少数几个人伤亡。
刘邦就这样占领了永城，朝廷一时还不知道，即使知道也顾不到这个地方。刘邦的首战就取得了大捷，感到很顺利很高兴，他就让手下在永城好好地享乐了一下，补足粮草，配备大量兵器，扩大了队伍规模，准备将来干更大的事。
刘邦是个很有头脑的人，没几天他就意识到永城再好，也不是久留之地。要想干成大事，凭自己手上的这点人马是根本不可能的。他就把永城交给了史劲来驻守，自己带着其余的队伍向北前进，决定带兵投靠正在攻打咸阳的陈胜、吴广。
有了攻打永城的经历，他认为只要是没有大量驻守秦军的地方，城池都很好攻下来，在经过曹县时，刘邦就决定对这里来一个突然袭击。不料，因为曹县附近起义军经常出没，守军早就加强了防范。他们进城之后，城门就迅速关上了。刘邦的几支部队，都遭到了猛烈的反击。他们无法占领官府，也无法控制城门，双方展开了激烈的肉搏战，最终都来到了城中间的大街上。刘邦眼看秦军众多，就命令队伍从南城门撤退。队伍一听要撤退，再无心恋战，大群人都涌向了南城门。由于守门的重兵刚才都冲向城中围堵义军去了，南城门这一会非常空虚，刘邦等人才侥幸逃脱。刘邦随后清点人数，队伍损失了大半，班头郝松也不见了。
刘邦很后悔没弄清情况就去攻打城池。他本打算等打下几个大城池后，把队伍壮大一些再去投奔陈胜。现在自己被打得七零八落，有何面目再去投奔别人？一时他们成了流寇，白天漫无目的前进，夜晚靠打家劫舍来抢口饭吃。
随着刘邦与项梁、项羽的起义，在江淮一带的广大地区很快就出现了反秦起义的热潮。秦二世二年，刘邦大破秦军围攻丰邑的部队，十一月，刘邦引兵至薛，再次大败秦军。正当刘邦的军队连战连胜之际，不料反秦的义军之间发生了争夺地盘的冲突，并导致了自己队伍的分裂。原来，受陈胜派遣北攻魏地的周市，这时竟南下至丰、沛一带扩展自己的势力范围。他借口历史上魏国曾经一度东迁于丰，竭力策动刘邦的手下雍齿背叛刘邦，归附于魏。雍齿本来就不愿追随刘邦，经周市的一番威逼利诱，便公开背叛刘邦。雍齿的背叛，无疑是对刘邦的一次巨大的打击。他率军猛攻丰邑，仍不能夺取，只得暂时退守沛城，积蓄力量，设法争取新的援助。
秦二世三年正月，秦嘉、东阳宁君等率领陈胜起义军的一支部队，结集在留城附近，他们的势力较强大。刘邦就去投奔秦嘉，请求他援兵攻打丰邑。但这时的形势突然发生了巨大变化，刘邦与东阳宁君主动引兵迎战。初战于萧西，出师不利；再战于砀山以南，激战三日，一举夺下砀城，并收编了大批砀郡的士兵。不久，刘邦又攻克下邑。经过近三四个月的战斗与磨炼，刘邦的部队已经发展到万人左右。他自觉实力已经明显得到增强，于是再度下令攻击丰邑，但是这次又未攻下。适逢这时项梁、项羽率领的数万大军已经进驻薛城，成为当时反秦起义军中一支最强大的力量。刘邦一方面为了自身的发展，另一方面也为了雪雍齿背叛之仇，北上至薛城，投靠了项梁、项羽大军。
