在刘秀派出邓禹和冯异平定关中的同时，刘秀便派遣大司徒伏湛的儿子伏隆为使节，出使了青、徐二州。代表刘秀告诉张步，封张步为东莱太守。
在更始帝败亡后，梁王刘永便自封为了天子，他不断地攻城略地，势力北至黄河，南至淮阳、汝南。他以苏茂为大司马，周建为大将军，又封琅琊的张步为齐侯，东海的董宪为海西侯。
刘永听说刘秀去招降张步，马上派人赶到了剧县，宣布立张步为齐王，张步便扣押了伏隆。伏隆秘密地上书刘秀，请朝廷早日出兵，不必顾虑自己，并要求刘秀照顾自己的父母和兄弟。刘秀流着眼泪把书信给伏湛看了，说伏隆堪比苏武。张步最终还是杀了伏隆，倒向了刘永的一方。
不久，刘永策反了睢阳的守军。刘秀急派吴汉前去支援盖延，然后两个人分了工，盖延包围了睢阳，吴汉包围了广乐。
刘永的部将周建得报，集结了十多万的人马，试图前来解围。吴汉初次迎战不利，从马上坠了下来，并且摔伤了膝盖，不得不回营养伤。周建便进入了广乐城。
吴汉手下的诸将，不无担忧地对吴汉说：“大敌当前，初次开战便伤了主将，如果再战，恐怕士气会受到影响。”
吴汉愤然而起，拿绷带简单地包扎了一下膝盖，便下令杀牛犒军，并进行了战前动员：“弟兄们！贼寇虽多，但都是一群乌合之众，撤退时比风还逃得快，让他们迂回包抄像树一样慢。但烧杀抢掠却像火一样的欢，当友军有难的时候，他们会像乌龟有样的缩。今天正是我们立功封侯的好机会，大家奋进啊！”
第二天，苏茂、周建主动出击，对吴汉进行了反包围。但吴汉手握着长戟，站在战车上大喊：“听到鼓声就冲，有慢的立刻斩首。”
只听得鼓声雷动，吴汉的军队一涌而出，把叛军冲得人仰马翻，广乐城被一举拿下了。
苏茂、周建逃奔了湖陵，吴汉回师同盖延合兵一处，又把睢阳围困了起来。
睢阳被围困了一百多天，城中粮食全部吃光，刘永只能开城门突围。但盖延紧紧地追赶，在中途斩杀了刘永。刘永的弟弟刘防，打开了睢阳的城门投降了。
苏茂、周建便拥立了刘永的儿子刘为紆梁王，转移到了垂惠城，继续进行着顽抗。
但是东线却又出了一件大事。
庞萌，原是更始朝封的冀州牧，当时他与谢躬同在邯郸，他对谢躬说：“刘秀这个人不可以信任。”谢躬便去试探了刘秀，但刘秀对他进行了抚慰。后来谢躬被杀，庞萌迫不得已，率众投降了建武朝。
刘秀便问庞萌：“你在邯郸的时候，怎么会这么了解我？”
庞萌低眉顺眼地说：“大王雄才大略，这我早就知道了。”
庞萌做人、说话的八面玲珑，很是得到了刘秀的欢心，刘秀甚至说：“这是一个值得托孤的大臣。”便又任命他为平狄将军，随盖延出征梁楚之地。
谁知公元29年，庞萌突然袭击了盖延，然后自称为东平王。与董宪、苏茂在一起结成团伙了。
刘秀大怒：“人心隔肚皮啊？我当初还说他可以做托孤大臣，这可让大家耻笑了。这个老贼应当灭了他的族。”然后刘秀下令，各路兵马到睢阳集结，御驾前往亲征。
刘秀到达了蒙县，探马报来桃城告急，因为庞萌、董宪、苏茂正在猛攻桃城。
刘秀便率轻骑两千，精兵数万。日夜兼程地赶去救援，不少大将却要求休整，但都被他拒绝了，刘秀一直走到了任城才宿营。
任城距庞萌的根据地东平不过一百多里，庞萌便严阵以待了。
尽管汉军将士们都摩拳擦掌，但刘秀却命令不得出战，这种情况看得庞萌目瞪口呆了。他说：“昼夜奔袭数百里，本来应该是来速战速决的，没想到他竟然坚守不出，这真是神鬼难料啊！”但刘秀召唤了在东郡的吴汉。
二十多天后，吴汉率军赶到，便与盖延、王常、王梁、王霸、马武奋勇出击。汉军气势如虹，一鼓作气把庞萌等杀得大败而逃，率领着残部退守到董宪控制下的昌虑，汉军啣尾而追，又团团围困了昌虑。
董宪见汉军势大，便找来了五校农民军余部驻守建阳城，与昌虑呈倚角之势。
刘秀深知农民军的习性，因为他们没有后勤的供给，当他们吃完了所带来的粮食，便会自行撤退。因此没有理会建阳城，果然不久，五校农民军粮断便退走了。
汉军四面围住了昌虑，奋力地进行了攻打，没有几天便攻破了。苏茂突围去投了山东的张步，董宪、庞萌逃进了山中，数日后聚拢了部众，又进入了郯县。
吴汉尾随而至，又破了郯城，董宪、庞萌又退守朐县，他们坐困在愁城。梁王刘纡在乱军之中，被军士高扈所杀。余众都归降了，在刘秀的亲自统师下，这一个割据势力，又被完全地削平了。
建威大将军耿弇奉命攻打张步，他表现出了极高的军事才能，他导演了东汉初年的一轮惨烈而又是极度出色的大战。
听说耿弇渡过济水，张步命他的大将费邑率军驻守历下，又分兵祝阿和泰山以北的钟城，排成了一个三角形的阵势。
耿弇先猛攻祝阿，不到半天就拿下了这座城池，然后故意放走了一队残兵，残兵逃到钟城，都为了表明不是自己无能，便极其夸张地进行了宣传，说耿弇青面獠牙、三头六臂。把钟城的守城吓得立刻弃城而跑了。
费邑的三角阵势如此轻易地就被破了。他急忙派弟弟费敢，去坚守巨里城，以保证后路畅通。但耿弇直扑了巨里城，他包围了巨里城以后，没有马上进行攻击。他命令士兵砍伐了许多树，又暗中放走了俘虏，扬言三日后破城。他引诱得费邑上了当，连夜率领精兵三万，驰援巨里。耿弇闻报，但只留三千人围住了巨里，亲率主力伏击费邑。
汉军居高临下直扑费邑军，势如破竹地击溃了费邑的三万精兵，并于阵前斩杀了费邑，然后高举着费邑等人的首级，向城中展示，巨里城中见主将已死，登时便土崩瓦解，耿弇扫清了残敌，遂平定了济南郡。
当时张步定都剧县，听说济南失守，便命令他的弟弟率精兵两万前往西安城，其它将领驻守临淄，两座城也相距四十里。
耿弇率军驻扎在两座城的中间，他了解到西安城城小而兵多，临淄城城大而兵少，他便故意扬言要攻打西安城。
但耿弇半夜造饭，天明前赶到了临淄，趁着清晨的晨曦，直接攻上了临淄。张蓝如同见到了天兵天将似的，惊慌失措地逃回了剧县。
耿弇又派小股军队，在剧县一带骚扰，他终于激怒了张步，张步于是和几个弟弟，率领着号称二十万的全部兵力，向临淄直扑而来。于是，东汉末年的战争史上，最最残酷的一场战役，便拉开序幕了。
耿弇担心敌军受挫后便会退却，他就故意示弱，佯装败退到临淄小城。当时的临淄有一个大城，都是平民百姓居住的，还有一个小城，却是富人成堆地居住的。正所以耿弇要退到临淄小城，因为城虽小，但墙高池深，易守而难攻。
耿弇让骑都尉刘歆守城，自己却站在故齐王宫的高台上观察。张步军正在猛攻北门，耿弇见敌军分散，全无准备迎敌时，他突然打开了东门，向张步军发起了反攻。张步军在毫无防备的情况下受到了反击，双方便发生了猛烈的战斗，战况极度的惨烈。张步军的死尸，居然把护城河都填满了。在战斗中，耿弇的大腿被箭射中，他一刀砍断了箭杆，继续指挥战斗。双方一直激战到日暮时分，耿弇率兵退回了城中，张步却驻扎在了城外。
部将陈俊听说刘秀的援军正在过来，便劝耿弇：“张步势众，你又受伤，可以先停战，等陛下援兵来到，然后内外夹攻。”但耿弇却说：“陛下假如来到，应当杀牛备酒庆祝，怎么能把强敌甩给陛下呢？”
第二天，耿弇依旧披挂上阵，杀得敌军尸横遍野，到了黄昏的时分，耿弇估计张步要撤退，于是便预先指派了两路伏兵。
夜幕降临，张步果然开始撤兵了，这时伏兵齐出，耿弇挥军奋力追杀，一直追杀了八、九十里，这八、九十里的路上僵尸相属，也就是说，在这八、九十里的路上，死的人一个连着一个，一直排满了这条八、九十里的路。
刘秀到了临淄，见状非常高兴，他大大地夸耀了耿弇一番，说他有志者事竟成。同时表露了愿意招降张步的意思。
耿弇追击张步到平寿，传达了刘秀的意思，张步走投无路，便杀了投奔自己的苏茂，赤裸着上身，自缚并背斧请降，刘秀接受了投降。但没有过多久，张步兄弟四人又重新谋反，流窜到了琅琊县，被琅琊太守陈俊抓捕斩首，于是，山东便宣告平定。