光武帝从桃城出发，辗转来到湖陵，探知董宪、刘纡合兵数万，占据昌虑，于是率兵攻打。庞萌、苏茂、佼强三人从桃城逃走后，辗转投奔董宪。董宪见部下越来越多，渐渐骄傲起来，戒备也松懈下来了。光武帝探知消息后，率领将士赶到昌虑，分头进攻董宪的大营。董宪慌忙分兵防备，勉强支持了三天，最终被汉军捣破营垒。董宪骑马逃走，庞萌与董宪一同逃往缯山。苏茂来不及跟随，投奔张步。刘纡趁乱逃出军营，只有佼强解甲投降。光武帝连得大捷，又派吴汉率军追剿。
董宪与宠萌从缯山逃出，招集一百多人，回到郯城。吴汉等人从后面追来，董宪、庞萌寡不敌众，自知守不住郯城，又逃往朐城。吴汉紧追不舍。朐城属东海郡，地势险要，储粮颇多，董宪、庞萌据险防守，吴汉倒也不能立刻拿下。刘纡东跑西走，厮混了好几天，被追随他的高扈砍下头颅，献给光武帝。
光武帝因梁地已经平定，乘便到鲁地祭祀孔子，并派建威大将军耿弇讨伐张步。张步听说耿弇将要到来，就让部将费邑屯兵历下，又分兵驻守祝阿，另外在泰山、锺城等地扎营防守。耿弇先攻打祝阿，半天就攻下了，却故意网开一面，让守兵逃跑。守兵一齐逃到锺城。锺城人听说祝阿失陷，当然恐惧，你也逃、我也走，只剩下几座营垒，寂静无人。耿弇并不去夺取，反而领兵攻打巨里。巨里由费邑的弟弟费敢把守，耿弇扬言三天就能攻破巨里。费邑听说后，担心弟弟失守，率领精兵三万前来支援巨里。耿弇得知后，高兴地对众将说：“费邑果然中计了，自己前来送死。”于是派三千将士直逼巨里城下，自己率精兵一万，在一座高山上做好埋伏。
费邑领兵前来，刚走到山下，听见山上一声鼓响，竖起一面大旗，上面有一个“耿”字随风飘荡，却没有一人下山。费邑等了很久，见没有人影，率众继续前进。山上的鼓声再次响起，几百个人突然出现在山顶，拿着兵器似乎要冲下来。费邑等了半天，却不见有人下来，刚要前进，鼓声越来越紧，旗帜越来越多，令人不知所措。随后猛听到一声呐喊，已有无数人马冲入军中。
费邑慌忙迎敌，无奈来兵气势汹汹，并且部下军心已经散乱，因此更加手足无措。费邑正要撤退，不料有一个大将策马前来，劈头一刀，费邑来不及躲闪，头颅已被砍下。军队失去了主帅，士兵顿时四处逃跑。斩掉费邑的大将正是耿弇。
费敢在巨里城，知道兄长要来支援，打算出兵接应，无奈城下有几千个汉兵堵住城门，也只好在城内安心等着。忽然汉兵大队人马赶到，先锋拿着一个血淋淋的首级。费敢一时难以辨认，只听汉兵大叫道：“这是费邑的头颅，你们看仔细了，如果再不出来投降，也要与这个头颅一样了！”费敢仔细一看，果然是兄长的人头，不禁痛哭流涕。守兵都很惊慌，无心防御，趁夜逃走了，费敢也赶忙逃回剧城。耿弇又接连攻下四十多座营垒，于是济南平定。
张步派弟弟张蓝领兵两万防守西安，又征集各郡将士一万多人防守临淄。两城相隔上千里。耿弇抵达画中，命令众将部署人马，约定五日后攻打西安。到了第五天，众将聚集在一起，接到的命令却是在第二天早上攻打临淄。护军荀梁因这次的军令与前次不一样，进帐问道：“以前说攻打西安，现在为什么转而攻打临淄呢？”耿弇答道：“西安虽小，却很坚固，张蓝的部下又都是精兵，不容易攻下。临淄似乎是个大城，守兵却是乌合之众，容易攻下。我以前说将要攻打西安，是声东击西的计策。现在不攻打西安，却去攻打临淄，是攻其不备，临淄一攻下，西安也难以守住了，一举两得。”荀梁默然退下。
耿弇乘夜出兵，直攻临淄，城内果然来不及防备，半天就攻下了。再转攻西安，张步已经逃回剧城。荀梁等人因此都很佩服耿弇。耿弇安抚百姓，严禁士兵骚扰民众，并传令说张步罪在不赦，如果他前来送死，务必生擒。这话传到剧城，张步大笑道：“我自领兵以来，战无不胜，尤来、大枪的十几万人都被我消灭了。耿弇的部下还不如他们，士兵又很疲劳，反而说出这样的大话，岂不可笑？看我与他交战，究竟谁胜谁负？”于是与三个弟弟张蓝、张弘、张寿以及降贼重异等率兵前来，号称二十万大军，抵达临淄城东，指日攻城。耿弇闭城自守，并不应战。
重异领着部下前来挑战，耿弇的部将想出去迎战，耿弇反而让各军退回小城，只派都尉刘歆及泰山太守陈俊，布兵列阵，在城下驻扎。重异认为耿弇不敢迎战，越逼越紧；张步也自恃人多势众，随后赶到，一起进攻刘歆、陈俊。刘歆与陈俊不得不战，于是双方交起手来。耿弇登高远望，见城外两军交战，立即率兵从东门出来，向张步的军队横冲过去。张步招架不住，忙令弓弩手放箭射向耿弇。耿弇用盾护着，继续战斗。突然一支箭射中耿弇的大腿，耿弇并不惊慌，继续战斗。张步毕竟人多势众，虽然死伤惨重，还是不肯退去。一直打到日暮，张步才战败退却。
光武帝当时在鲁地，接到耿弇的书信后，放心不下，于是领兵东行，亲自去救援耿弇。耿弇正准备与张步再战，恰逢张步率兵到来，双方从早上打到傍晚。耿弇料到张步将要退兵，就派一部分人绕到张步身后，埋伏在两旁。等到天黑，张步果然率兵退去，伏兵突然杀出，张步抱头先逃，后面的部下都做了无头鬼。
过了几天，光武帝来到临淄，耿弇率领众将跪在路边迎接。光武帝当面慰问几句，令耿弇等人起身进城。光武帝因耿弇打了胜仗，格外高兴，于是大摆宴席，犒赏群臣，并当面嘉奖了耿弇。休息了一夜，光武帝便与耿弇一起攻打剧城。张步打了败仗，才知耿弇谋略过人，不可力敌。又听说光武帝亲自指挥，更加惊慌。张蓝、张弘、张寿比张步还胆小，分别领兵离去，张步随后也弃城逃走。城中没有了主帅，自然开门投降。耿弇来不及进城，又领兵追赶张步。张步逃往平寿，碰巧苏茂招集旧部共有一万多人，前来支援张步。
不久，耿弇率兵赶到，张步不敢迎战，只是与苏茂坚守。光武帝派人告诉张步，如果他杀了苏茂前来投降，就封他为列侯。张步于是将苏茂杀死，出城投降。耿弇把张步送到剧城，请光武帝发落，自己则进城安抚军民。耿弇见张步还有十万部下，军用物资七千多车，当场拿出一些钱财分发给张步的部下，让他们离去。张步到了剧城，叩头谢罪，光武帝没有食言，封张步为安邱侯，并传诏赦免张步的弟弟。张蓝、张弘、张寿相继归降，琅玡太守王闳也举城投降。光武帝提升陈俊为琅玡太守，并派耿弇消灭剩余的盗贼；自己带着张步回都，令张步与妻儿一同住在洛阳。
陈俊进入琅玡境内，盗贼立马散去。耿弇攻到城阳，五校余党全部投降。齐地平定以后，耿弇领兵还朝。张步在洛阳居住不久，又起了反叛之心，悄悄带着妻子儿女逃到临淮，想再次招集旧部，结果被琅玡太守陈俊杀死，全家都死于非命。
转眼就是建武六年，光武帝收到两个捷报。李宪占据庐江郡，自称淮南王，建武三年，居然称帝，设置九卿百官，管辖九座城池，部下有十多万。第二年，汉扬武将军马成奉诏讨伐李宪。马成，字君迁，南阳郡棘阳县人。光武帝让他协同诛虏将军刘隆、振威将军宋登、射声校尉王赏，调发会稽、丹阳、九江、六安四郡兵马，进攻舒城。舒城是李宪的根据地，守备甚严。马成到了城下，巡视一遍，见此城不容易攻下，就选了一个地方安营，只求自守，不求进攻。马成把情况上报给洛阳，说须等到一两年后，才能将敌人消灭。光武帝准许马成见机行事，马成于是坚守不动。李宪多次出来挑战，马成始终严守，数月不同李宪打仗，只是分兵袭击李宪的粮道，然后逐渐围城，四面筑起栅栏，以守为攻。李宪派兵突围，但多次被击退。直到建武六年，城中没有了粮食，马成才鼓舞将士，奋力攻城。不到十天，便将城池攻破。李宪拼命杀出重围，连妻儿都来不及带走，落荒而逃。马成将李宪全家杀死，又派人追捕李宪。过了两天，有人拿着人头前来投降，问明情况，原来是李宪的部下杀死了李宪。马成乘势攻占这九座城池，江淮最终得以平定。马成凯旋回朝，晋封为平舒侯。
同时，吴汉攻下朐城，抓住了董宪的家人。董宪与庞萌连夜逃到赣榆，琅玡太守陈俊听说后，率兵前去攻打。董宪、庞萌途穷末路，再次仓皇逃走，随从只有几十个骑兵。董宪不禁欷歔道：“数年称王，一朝被灭，妻儿都被逮去，国破家亡，还有什么好说的呢？”说到这里，对随从骑兵说：“你们追随我数年，被我拖累，竟得到这样的结局，岂不可怜？”骑兵听了这话，都悲伤不已。突然看到后面尘土大起，又有追兵杀来，董宪、庞萌慌忙奔逃。快到方舆时，被来将追上，董宪被杀，首级由来将取走。来将是吴汉部下的校尉韩湛，韩湛斩了董宪的首级，又去追赶庞萌。庞萌从乱军中逃出，逃到方舆人黔陵家内。黔陵见他狼狈不堪，一再盘问，庞萌才说出真实姓名。黔陵假装留他住宿，趁他睡熟的时候，将他杀死，并把首级送到吴汉军前。吴汉将董宪、庞萌的人头送到洛阳，并报明韩湛、黔陵二人的功劳，二人都被封侯。
山东平定后，各将士奉诏西归，光武帝开始谋划西征。