虽然如此，但司州统辖的淮西七郡（汝南郡【河南省汝南县】、新蔡郡【河南省新蔡县】、汝阳郡【河南省商水县西北】、陈郡【河南省淮阳县】、汝阴郡【安徽省阜阳市】、南顿郡【河南省项城县西南】、颍川郡【河南省许昌市东】）百姓却不愿意投降敌国，他们携家带口，纷纷南下。北魏朝廷派遣建安王、散骑常侍陆馛到新占领区安抚这些惊恐不安的百姓，他下令把魏军掳掠为奴婢的人全部恢复自由，这样以来，这里的百姓才高兴起来。陆馛，是陆丽的大哥，原为相州刺史，是北魏出了名的良吏，当时北魏官吏尚无工资，大多数人都是靠贪污受贿、战争掠夺养家，陆馛在相州为官七年，为政清平，由于他非常廉洁，家境十分贫寒。拓跋弘继位后，征召陆馛入京，一千多名当地百姓上书请求留下他，拓跋弘没有同意，但却对群臣感叹道：“陆馛的善政，即使古人也超不过呀！”赏赐给他五百匹绢、十个奴婢。陆馛临行，当地百姓自发捐献给他很多布帛，但他一点都不接受，于是，百姓们把这些财物建造了一座佛寺，取名为长广公寺。长广公是陆馛继承父亲陆俟建安王之前的爵位。
淮西方向逐渐安定，但淮北方面却面临着一场血战，这是因为，彭城战略位置非常重要，假设魏军占领了彭城，进而控制淮河下游，切断刘宋帝国青州兖州与淮南的联系，使得山东地区孤悬于外，迟早会被吃掉，这样以来，刘宋帝国不仅失去了大量国土，而且，其北部边境将由淮北转移到淮南，丢掉刘裕多年以来占领的山东地区，势必在攻守两方面都处于不利局面，因此，宋明帝对此也高度重视，当得知薛安都投靠北魏前后，即发兵前往讨伐。
当魏军东路军统帅尉迟元率部进抵彭城以北九里山之时，薛安都率领徐州文武前去迎接。见面之后，尉迟元对薛安都一行却非常傲慢，薛安都回城之后，即将魏军晾在了一边，再也不派出使者。当时，刘宋讨伐军张永、沈攸之所部已经迅速推进到了彭城东南近郊的下磕（江苏省徐州市东南），另外派遣羽林监王穆之率领五千精兵驻扎在武原（江苏省邳州市邳城镇泇口街道）守卫辎重，龙骧将军谢善居率领两千人马驻守吕梁（江苏省徐州市铜山区东南吕梁集），散骑侍郎张引率领两千人马驻守茱萸（江苏省徐州市铜山区东北），督促百姓上缴粮食，供应部队。下磕距离彭城最近，在彭城的东南，下磕西南是茱萸，茱萸再往东南是吕梁，下磕的正东是武原。一说，宋军的辎重在武原，米船在吕梁，《水经注》称：“泗水自彭城东南过吕县南，泗水之上有石梁焉，故曰吕梁。”
一场恶战行将爆发，此时，假如薛安都有所动摇，长途而来的魏军野无所掠，又深入帝国国境，势必面临覆灭的危险，尉迟元想到这，赶紧派遣中书侍郎高闾、李璨等人入城劝说薛安都，薛安都这才再次出城，来到魏军军营。薛安都一入魏营，即身不由己了，魏军挟持着他，由孔伯恭率领两千精兵先行进入了彭城，安抚内外，接管城门，很快就控制了整个彭城，随后，魏军主帅尉迟元这才率军迅速进入城内。当天夜晚，宋军张永所部即对彭城南门发起了夜袭，但无功而返。
入城之后，尉迟元依然对薛安都不理不睬，很不礼貌，这让薛安都非常后悔，打算再度背叛北魏，但薛安都的阴谋却被尉迟元发现，没有发动。薛安都拿出巨额钱财贿赂尉迟元等将，将罪过推给了女婿裴祖隆（原来驻防下邳【江苏省睢宁县古邳镇东】），于是，尉迟元即将其诛杀，隐瞒下薛安都的阴谋。
面对彭城城外屯据三地的宋军，尉迟元认为张永所部人多势众，是宋军主力，并且占据了险要，强攻起来胜负难料，于是，他采取了先弱后强、各个击破的战法，命令薛安都、李璨等人固守城池，他亲自率领精锐部队，声东击西，出其不意，突然南下进攻距离彭城最远、也是最弱的吕梁的谢善居所部。谢善居所部仅仅两千多人，其任务也只是在后方征收粮草，本来就不属于战斗部队。突然遭到魏军主力打击，谢善居战败，被逃至茱萸，又与在这里的张引所部一起东逃到武原。魏军纵马追击，斩杀了八百多宋军。
魏军初战告捷。李璨劝说尉迟元派兵进攻武原的宋军辎重，于是，尉迟元派遣猛将吕洛拔率部东去。魏军的动向立即引起了宋军主帅张永的注意，他也派遣部将周山图率领两千部众增援武原。一场猛将对猛将的恶斗随之展开。双方恶斗了整整两天，吕洛拔亲手格杀了九人，魏军抢到了二百多辆粮车，二百五十头牛；而周山图率领的迎接粮车之军，在魏军骑兵的追击下，边打边撤，固守一座小山包，布下了营阵，然后，突出重围，所向披靡，魏军无法抵挡，周山图因此也被魏军尊称为“武原将”。
也许是谢善居和张引的迅速败退，让尉迟元产生了错觉，而周山图所部的勇猛，让他不得不重新审视宋军的战斗力。玉于是，尉迟元再次亲自率领魏军主力，弃眼皮底下的张永主力于不顾，长途奔袭，再度朝武原扑来。魏军从四面八方朝武原发起了猛烈的进攻，王穆之率领八千宋军与敌人展开了殊死搏杀。霎时间，遍地狼烟，箭如飞蝗，杀声四起，经过激战，宋军死伤大半，魏军终于攻陷了武原外城，斩首数千级，缴获宋军辎重五百多辆，用以接济彭城驻军。宋军辎重尽失，魏军目的已经达到，于是，尉迟元下令暂缓对武原内城发起攻击，给王穆之的残余部众开出一条生路，王穆之率领残余部众向西逃归了张永大本营。
尉迟元避实击虚，切断宋军粮道，并全力拿下宋军辎重集结地武原，与曹操在官渡之战中夜袭乌巢，烧毁袁绍军淳于琼部防守的辎重，几乎如出一辙，都起到了四两拨千斤的效果。在天寒地冻中丧失了辎重的宋军生存已成问题，更不用说打仗了。
泰始三年（公元467年）一月，新年刚过，尉迟元就乘胜率军将下磕城包围，对下磕南门发起了进攻，张永已经毫无办法，只得趁夜率军撤离。不幸的是，天上突然下起了大雪，泗水结冰，宋军所有战舰都无法行动，原来从水路而来、习惯于水战的宋军不得不丢弃战舰，从陆路败逃。隆冬季节，仿佛让鲜卑骑兵们回到了他们熟悉的北国，而对于长期生活在水乡泽国的江南将士们而言，就象是来到了陌生的异域，再加上饥肠辘辘，张永所领的刘宋精锐之师顿时丧失了战斗力。
在张永决定撤退之前，尉迟元已经预料到宋军即将南逃，他提前命令魏军骑兵切断了宋军的归路，命令薛安都率领彭城步兵在后赶杀。在黑夜中夺路而逃的宋军遭到南北夹击，一场残酷的屠杀随之在茫茫的雪夜里展开……
魏军在吕梁东面大破宋军，斩首数万级，在南北六十里长的范围里，数万宋军尸体一个挨着一个，其中，在被杀前，因严寒手脚被冻掉的宋军将士就占十分之八九！（《魏书·李璨传》称“永军冻死者万计”，《宋书》称：“士众堕指十二三。”）生擒刘宋使持节、都督梁南北秦三州诸军事、梁秦二州刺史、宁朔将军、益阳县开国侯垣恭祖；龙骧将军、羽林监沈承伯等人；宋军主帅张永、副帅沈攸之跨马狂奔，仅以身免，魏军缴获的战舰、车辆、军资、武器不可胜数。轻骑走免。收其船车军资器械不可胜数。