但是，刘邦一家的转折来了！
在公元前209年，秦末农民起义爆发，陈胜、吴广率领起义军攻占了陈县以后，陈胜建立了“张楚”政权，和秦朝公开对立。
秦二世元年秋，陈胜等起蕲，至陈而王，号为“张楚”。
这是短短的一句话，让华夏人知晓了，帝王将相宁有种乎！
这时，沛县令也想响应起义，萧何和曹参当时为沛县吏，他们劝县令将本县流亡在外的人召集回来，一来可以增加力量，二来也可以杜绝后患。
县令觉得有理，便让樊哙去邀请刘邦，刘邦当时已拥数百之众。
然而此时沛令却又后悔了，害怕刘邦回来不好控制，弄不好还会被他所杀，等于是引狼入室。
所以，他命令关闭城门，并准备捉拿萧何和曹参。二人闻讯赶忙逃到了城外，刘邦闻此，于是将一封信射进城中，鼓动城中百姓起来杀掉出尔反尔的县令，大家一起保卫家乡。
百姓对平时就不太体恤他们的县令很不满，杀了县令后开城门迎进刘邦， 萧何、曹参都是文吏，担心身家性命，深恐举事不成，被秦朝诛灭九族，就竭力推举刘邦来领导大家起事。
大家推举他为沛县县令，依楚制称作沛公。
刘邦便顺从民意，设祭坛，立赤旗，自称赤帝子，很快义军扩充到三千人。
此时，已经是公元前209年10月，刘邦已经48岁或39岁了 。
秦末农民战争中还有一支强大的力量，就是原来楚国贵族的后代项梁和项羽。
他们在吴中（今江苏苏州）起兵，兵力很快达到了近万人。
刘邦起事后，立即开始攻略周边郡县，先是攻胡陵、下方与，与泗水郡监平大战于丰邑，破之。
这时泗水卒史周苛、周昌兄弟加入到刘邦阵营。
刘邦接着令雍齿守丰，自己率领军队进入薛县，与秦军大战。
郡守壮战败，逃至戚，沛公麾下左司马追斩壮。
接着刘邦率军返回亢父、方与，以曹参守方与。这时魏相周市来攻方与，曹参率军迎之。
但是雍齿却据丰降魏。
雍齿也算是刘邦的发小，但他们两个从小就不对付，见面就打仗，看彼此都不顺眼。
但是，雍齿也是大汉知名的统帅，比起周勃他们统帅能力还要出色，日后刘邦防着韩信就是用这个家伙。
韩信也是被雍齿搞得十分难受。
听到发小叛变，刘邦大怒，进攻丰。
雍齿据城以守，沛公军不能攻下丰邑，恰在此时，刘邦生病，于是还军至沛。
这时，刘邦闻东阳宁君与秦嘉立景驹为楚假王，在留县（今沛县东南），于是投奔景驹，欲借军攻丰。
在去投奔景驹的路上，遇见了也要投奔景驹的张良。
两人于是兵合一处。
张良与刘邦二人见面后，一交谈，两人大有相见恨晚之意。于是张良放弃投奔景驹的念头，直接投奔到刘邦这边。
刘邦以张良为厩将。
这时秦朝章邯的部将司马夷攻略楚地，屠相（今安徽HB市），至砀（今永城芒山镇）。
于是沛公与东阳宁君率军向西，迎击司马夷，在萧县西与秦军展开战斗，结果不利，刘邦与东阳宁君退至留。
补充军队和粮草后，再次进攻秦军，三日取砀，得到军卒六千人。接着乘胜攻取了下邑（今安徽砀山县）。
这次，刘邦认为自己军队差不多，从下邑出发，再次攻丰，结果仍然没攻下。
这时听说项梁在薛，于是留下军队围丰，自己率领百余骑至薛见项梁。
项梁为沛公增兵五千、五大夫将十人，三攻丰邑。
雍齿不敌，逃奔魏国。
刘邦从属项梁一个多月后，项羽攻下襄邑也还至薛。当陈胜死亡的消息被证实，项梁把别将全都召回薛县，采纳范增的建议，立战国时楚怀王的孙子熊心为楚王，仍号楚怀王，定都盱眙。
楚怀王任命陈婴为上柱国，项梁号武信君。
这时的刘邦，是屁都没有混到，只是一名杂号将军。
不过，也算是找到组织了！
拥立楚怀王后，项梁率军北上救齐赵，在亢父、东阿大破秦军。
这时齐军因田间、田都、田角的缘故，引兵返回齐国。只有楚军追击秦军。
在这期间刘邦军团与秦国将领章邯的车骑部队交战，将其击退，平复蒙邑、虞县、爰戚县、东缗县、栗县、啮桑县、宛朐县、单父县等大量秦军占领的魏国城池，史称“定魏地”。
项梁下令楚军分军，以刘邦、项羽为帅，率楚军一部攻城阳。刘项二人率军攻下城阳（即成阳，今山东HZ市东），屠之。
然后追击秦军至濮阳东，再次大破秦军。
秦军这时得到补充，军势复振，守濮阳、环水。刘项二人不与之战，绕过进攻定陶。定陶未攻下，向西攻打雍丘（今杞县）。
沛公部将曹参大破秦兵，斩杀三川守李由，并俘虏秦侯一人。
之后，刘项二人还攻陈留，未下。这时秦将章邯大破项梁于定陶 （今山东定陶），项梁本人亦战死。
刘项二人大惊，两人商量后决定放弃陈留，还军东归。刘项二人分兵，项羽军驻彭城西、吕臣军驻彭城东，而沛公军驻砀郡。
项梁之死，使诸侯震怖。
而秦军更是挟战胜余威常追亡逐北。
章邯经过一连番胜利，认为楚国已不足虑，于是北上进攻赵国。
攻下邯郸后迁其民于河内，而赵军退守巨鹿，章邯率军进围赵王歇与赵相张耳于巨鹿。
楚怀王把都城由盱眙迁至彭城，将吕臣与项羽的军队合并起来自己统领。
封沛公刘邦为武安侯，升任砀郡长，统率砀郡兵马。
封项羽为长安侯，任鲁公。以吕臣为司徒，其父吕青为令尹。
经过一番调整之后，楚国局势稳定下来。
刘邦此时已被封为郡长（郡守），统筹整个砀郡旧魏地区兵力，其地位实际比项羽的县公（县令）要高。
楚怀王也不是傻子，遗老遗少也快速地聚集在他的身边，也让他有了一定实力。