赤眉投降后，关中无主，盗贼乘机兴起。下邽有王歆，新丰有芳丹，霸陵有蒋震，长陵有公孙守，谷口有杨周，陈仓有吕鲔，汧骆有角闳，长安也被张邯占住，他们都自称将军，互相攻打。延岑占据杜陵，打败赤眉将领逄安，然后率兵进入蓝田，自称武安王，想做关中霸主。延岑听说征西大将军冯异领兵前来，就同张邯等人前去截击，一番交战，反被冯异杀死一千多人。张邯战败逃跑，延岑也向东南逃去。冯异驻扎在上林苑，延岑的部下都向冯异投降。冯异又派邓晔辅助于匡追赶延岑。到了析县，正值延岑率领部下围城，一看邓晔等人到来，慌忙调头迎敌。可他的部下已经害怕，不敢再战，苏臣等人率先投降。延岑不敢再打，逃回南阳，又被耿弇等人迎头截击，斩杀三千多人，生擒将士五千多人。延岑势孤力单，投奔秦丰。
邓奉本是光武帝的姐夫邓晨的侄子，因征战有功，被封为破虏将军。吴汉攻打南阳时，士兵虐待百姓，连邓奉的故乡新野县也遭到蹂躏。邓奉回乡时，见到这种场面，十分恼怒，便纠集流氓，造起反来。积弩将军傅俊、骑都尉臧宫奉命与岑彭一起攻打邓奉。邓奉抵死相斗，双方互有死伤。后来光武帝亲自前来接应，汉军士气大增，邓奉无路可逃，只好投降。光武帝念及邓奉以前的功劳，加上事情是由吴汉引起的，打算赦免邓奉。岑彭与耿弇进谏说：“邓奉胆敢造反，罪无可赦！不杀他，怎么能让人信服呢？”光武帝不便徇私，只好将邓奉正法。随后，光武帝起驾还都，命岑彭与傅俊、臧宫等人向南攻打秦丰。
过了一个月，虎牙大将军传来捷报，说刘永被杀，睢阳平定。刘永在睢阳称帝，内有沛人周建等爪牙，外有佼强、董宪、张步等羽翼，除国都睢阳外，济阴、山阳、沛楚、淮阳、汝南等二十八城，都归刘永管辖。光武帝曾封盖延为虎牙大将军，让他与降将苏茂一同东征。苏茂本是刘玄的部将，曾与朱鲔共同防守洛阳，朱鲔投降后，苏茂也随之归附。后来，苏茂随盖延东行，因不肯受盖延控制，便分军自去，攻占了几个县城，反向刘永称臣。刘永任用苏茂为大司马，封为淮阳王。
盖延单独进攻睢阳，并且上奏说苏茂反叛，光武帝派驸马都尉马武、骑都尉刘隆、护军都尉马成、偏将军王霸等人做盖延的副将。双方又相持几十天，盖延尽收田间的小麦作为军粮，守兵因缺少粮草，渐渐畏惧，盖延乘机攻进城去。刘永不知所措，从东门逃走，另派骑兵几十人保护家属，逃往虞城。虞城人不愿接纳刘永，反将刘永的母亲及妻儿杀死，刘永仓皇逃脱，抵达谯邑。刘永的部将苏茂、佼强、周建等带兵三万，到谯邑营救刘永。盖延接连夺下薛城、沛城，斩杀鲁郡太守梁邱寿及沛郡太守陈修，追赶刘永。刘永率领苏茂等三位将军，到沛西迎战，又打了一个大败仗，只好放弃谯城，逃往湖陵。苏茂领兵返回广乐，只有佼强、周建与刘永同行。
盖延乘胜收复沛楚、临淮各城。光武帝派大中大夫伏隆到青、徐二州招抚。青、徐二地的盗贼多半投降，就是琅玡盗贼张步也归附汉朝。光武帝升伏隆为光禄大夫，封张步为东莱太守。哪知刘永听说后，忙派人立张步为齐王，并封东海的盗贼董宪为海西王。张步贪恋王爵，想违背以前的约定。伏隆探知隐情后，对张步说：“高祖曾与天下定约，非刘氏不能封王，你如果为朝廷效命，还能做个万户侯，何必接受伪封，只顾眼前，不顾日后呢？”张步不以为然，还想将伏隆也留下来，伏隆愤然说：“你不接受朝命，必定后悔！我奉命到此，岂会跟着你依附逆贼？我据实回报便是了。”说着，就想离开，张步却指挥左右把伏隆抓住，把他幽禁起来。伏隆写好书信，交给从吏，让他乘机脱身，回报朝廷。从吏乘夜逃出，回到洛阳，把伏隆的书信呈递进去。
光武帝看完后，急忙召来伏隆的父亲伏湛，把伏隆的书信给他看，并哭着说：“伏隆的忠诚可以与苏武相比，朕只恨他没有暂且答应，为自己寻求一条生路啊！”伏湛哭着退下。伏湛是济南伏胜的第九世子孙，光武帝即位后，听说伏湛有才，封他为尚书。现在因伏隆被抓，为了宽慰伏湛，光武帝提升伏湛为公卿。当时邓禹早已回到都中，自愧没有立功，交上大司徒及梁侯的官印。光武帝赐还侯印，只削去了大司徒一职。此次要提升伏湛，正好让他接任大司徒。不久光武帝又封伏湛为阳都侯，然后调遣大司马吴汉，以及骠骑大将军杜茂等，一同攻打刘永，并打算另派将领专门讨伐张步。忽然幽州牧守朱浮派人告急，请求派兵援助，光武帝因此无暇东顾。
朱浮告急是因为彭宠造反，逼近幽州。彭宠本是渔阳太守，曾帮助光武帝打败王郎。光武称帝后，封赏功臣，吴汉、王梁等人都位列三公，彭宠却没有得到提升，因此愤愤不平。幽州牧守朱浮喜欢结交宾客，曾向渔阳征集银米。彭宠不肯给，朱浮便写信责备他，彭宠从此忌恨朱浮。朱浮又上书弹劾彭宠，光武帝于是召彭宠入都。彭宠请求与朱浮一同入都，光武帝不准，彭宠因此更加怀疑。彭宠的妻子劝彭宠不要前往洛阳，彭宠因此没有应命。
彭宠出兵两万攻打朱浮，听说上谷太守耿况也是功劳大赏赐少，与自己的情况一样，就一再派人到上谷邀他一起造反。哪知所派的使者有去无回，都被耿况斩了。光武帝听说后，曾命游击将军邓隆领兵援助朱浮。可惜邓隆的营垒与朱浮相距太远，彼此照应不上，被彭宠的士兵趁机攻破，邓隆仓促逃脱，部下多半被杀。朱浮不能相救，只好守住蓟城，与彭宠抗拒。不久，涿郡太守张丰也与彭宠合兵，自称无上大将军。彭宠得到一个帮手，气焰更加嚣张，索性大举围攻蓟城。朱浮不敢出来迎战，只好飞书洛阳，乞求援助。
光武帝想了几天，一时腾不出兵马粮饷，只好让来使回去禀报，令朱浮只守不战，等筹足军粮，就去援助。朱浮坚守了好几个月，城中粮食已经吃光，外面却越攻越猛。多亏上谷太守耿况派来三千骑兵，冲破围城一角，朱浮才趁机杀出。蓟城的吏民来不及跟随，只好投降彭宠。彭宠得到蓟城后，又攻陷右北平、上谷等县，自称燕王，并北通匈奴、南给张步，召集残贼，称霸一方。
光武帝想去讨伐彭宠，又想到刘永还未消灭，如果远征，难免顾此失彼，所以只希望盖延、吴汉二军，早日平定刘永，然后再向北进军。偏偏好事多磨，睢阳城本来已经攻下，只有刘永一人逃脱。等盖延前去攻打沛楚，睢阳人竟开城迎入刘永。盖延再去围攻，没有得手。吴汉走到广乐，与苏茂交战数次，苏茂战败，逃入城中。吴汉率兵猛攻，四面架起云梯，将要登城，不料周建带着十几万人，前来援救广乐。吴汉率领骑兵前去截击，虽然敌众我寡，不曾胆怯，但最终还是打不过苏茂。眼看就要失败，吴汉不禁恼怒，一马当先，刺死敌兵数人。突然飞来一箭，射中马头，马负痛一蹶，把吴汉掀翻在地，多亏左右将士上前营救，才将吴汉扶回。吴汉膝上受伤，不能站立，众将只好闭垒自守，任由周建入城。
到了晚上，杜茂进去对吴汉说：“大敌当前，你若卧病在床，恐怕会动摇军心。”吴汉听了，勉强站起，走出帐外对将士们说：“敌人虽多，但都是乌合之众，现在正是你们立功的时候，杀贼封侯，在此一举，希望你们再接再厉，奋勇向前。”部下受到鼓舞，士气大振。到了天明，城中有角鼓声传入吴汉营中。吴汉知道周建等人又来挑战，便挑选精兵作为前锋，自己跟随众将出来迎战，并下令全军，听到鼓声一齐前进，退后者立斩不赦。吴汉布置好一切，打开营门，严阵以待。望见周建领兵出来，吴汉亲自擂鼓，鼓舞士气，前锋奋勇杀敌，后军紧紧跟随，一股脑儿冲入周建军中。周建抵挡不住，立即返回，被吴汉的部下快马追上。守兵来不及关门，结果全城沦陷，周建、苏茂逃跑。
吴汉进城安抚百姓，留下杜茂、陈俊防守，自己率兵追赶周建、苏茂，直抵睢阳。周建与苏茂进城拜见刘永，一同守御。吴汉与盖延合兵，日夜猛攻。城中被困了将近一百天，再加上周建、苏茂的败兵从外面逃进来，人数虽然越来越多，粮食却越来越少，无奈之下，只好保护刘永突围逃走。盖延从后面追击，刘永等人拼命乱跑，快到酂城时，刘永的部下已经四散逃去，连周建、苏茂也各自逃命去了，只有部将庆吾还跟着刘永。庆吾见刘永不能成事，于是眉头一皱，计上心头，悄悄拔出佩刀，向刘永脑后劈去，刘永未曾防备，当场被砍死。庆吾枭了刘永的首级，献给盖延。盖延令庆吾拿着刘永的人头入都，庆吾因此被封侯。
刘永的弟弟刘防守御睢阳，听说刘永已死，也开城投降。刘永的儿子刘纡跟着周建、苏茂一同抵达垂惠。周建、苏茂立刘纡为梁王，企图东山再起。刘纡派人到剧城，报告情况。剧城是张步居住的地方，他见刘纡派来使者，就想尊刘纡为帝，自称定汉公。因琅玡太守王闳极力劝阻，张步才打消这个念头，只将来使遣回。张步既不愿听命于刘纡，又不肯归顺洛阳，还杀死洛阳使臣伏隆，据地称雄。