在蔡洲静驻了好几天，卢循、徐道复见石头城畔的军容井然有序，没有一丝慌乱，不禁有些后悔，忙派发十多艘战舰攻打石头城外的防护栅栏。刘裕下令用神臂弓迎敌，一发数箭，敌船无不摧毁，卢循只好退去。不久，卢循用调虎离山之计，攻扑石头城，但仍旧碰壁；转攻各郡，各郡守都早已加固壁垒。卢循见毫无所得，便对徐道复说：“我军已疲惫不堪，不如退据寻阳，合力攻取荆州，然后再来谋取建康吧。”随即令贼党范崇民率五千名士兵据守南陵，大军则退往寻阳。
晋廷封刘裕为太尉中书监，并赐给他一把黄钺。刘裕随即保荐王仲德为辅国将军，刘钟为广川太守，蒯恩为河间太守。让他们与谘议参军孟怀玉率兵追击贼众，自己则操练水军，广修战舰。楼船一修成，刘裕便令将军孙处、沈田子率领一百多艘战舰走海路，径直奔往番禺，直捣卢循的老巢。各位将领认为海路迂远，也十分艰险，并且容易分散兵力。刘裕笑而不答，只是嘱咐孙处说：“十二月大军必破妖虏。你们先捣破贼巢，使他们走投无路，到那时，贼人自然手到擒来！”孙处等人只好领命而去。
卢循回到寻阳想方设法联络谯纵，约他夹攻荆州。谯纵当即答应，并向后秦求援。秦主姚兴封谯纵为大都督，兼相国、蜀王，并调桓谦协助他。谯纵任命桓谦为荆州刺史，谯道福为梁州刺史，令二人率两万多名士兵入侵荆州。后秦将军苟林也奉秦主姚兴之命率骑兵赶来会师。一时间，卢循声势十分浩大。
卢循率兵东下时，荆、扬二州有些闭塞，还不知道这一消息。当卢循退而攻打荆州时，荆州刺史刘道规正派司马王镇之前去，会合天门太守檀道济、广武将军到彦之，一同去援救建康。途中，王镇之突然遭到后秦将军苟林与卢循的夹击，一阵拼杀，王镇之败退。卢循重重犒赏秦军，令苟林进攻江陵，苟林随即入驻江津。桓谦也召集两万贼众，进据枝江。敌众两路大军交逼，江陵大震，城中的兵民大多怀着观望的心态。刘道规默察民情，索性大开城门，令士兵自行选择去留，同时严阵等待敌寇。士兵不禁惮服，没有一个人出逃，城中十分安定。
当时，鲁宗之已升任雍州刺史，自襄阳率兵前来支援荆州。有人说鲁宗之不安好心，刘道规却毫不在意。他不但单骑出城，将鲁宗之迎入城中，与他开怀畅谈，甚至还让他留守荆州城，自己则亲自带兵出击，讨伐贼人。大军水陆并进，在枝江击毙桓谦，苟林闻风而逃。参军刘遵奉刘道规之命追击，在巴陵一带击毙苟林。
刘道规返回江陵，刚送走鲁宗之，就收到徐道复率领三万士兵长驱而来的消息。当时，已经来不及追回鲁宗之军，刘道规只得部署各军，准备迎战。碰巧刘遵得胜而归，于是一前一后的两支军队，杀得轻敌的徐道复大败，逃回湓口。江陵转危为安。
刘裕听说江陵无恙，贼众连吃败仗，便令刘毅监管太尉府，全权处理府内事务，然后亲自率领刘藩、檀韶等将领南讨贼党。大军刚出发，便接到王仲德的捷报，说已赶走悍贼范崇民，夺回南陵。刘裕很是欣慰，当即赶到南陵城与王仲德会师，进军雷池。在雷池一带，刘裕军杀得卢循孤舟窜往番禺，徐道复退守始兴。晋将军刘藩、孟怀玉不依不饶，继续追剿卢、徐两贼，刘裕则率余军凯旋而归。晋安帝要封刘裕为大将军、扬州牧，并赏他二十名仪卫，刘裕推辞说：“卢循、徐道复两贼还没有除掉，臣怎么能接受陛下的封赏？”晋安帝于是收回成命。
在逃亡途中，卢循一路上召集了不下万人的残众，准备退回番禺。徐道复也召集兵马，退守始兴。只是始兴虽然安然无恙，番禺却早已落入晋军手中。卢循听说巢穴已被攻破，惊慌失措，忙率部众与晋军争抢番禺，却被晋将军孙处、沈田子、刘藩击败。卢循慌忙逃往南方的交州，最后在晋军的堵截中投水自尽。徐道复也被孟怀玉斩杀。南方逆党，至此都被荡平。
不久，荆州刺史刘道规因病请求离职。晋廷派刘毅前往荆州继任刺史，调任刘道规为豫州刺史。刘道规在荆州数年，秋毫无犯，体恤百姓，没想到调到豫州不久，就病逝了。荆州人得知，都垂泪不已，很是伤心。
刘毅自豫州战败后，虽然在刘裕面前谦逊不少，但心里却越发猜忌他。刘裕向来不善舞文弄墨，刘毅却很有文才，所以朝中词臣都喜欢与刘毅交往。仆射谢混、丹阳尹郗僧施与刘毅往来尤为密切。刘毅出任荆州刺史后，将刘道规之前施行的政策尽改无遗，又将豫州文武旧吏调到荆州，安置在自己麾下；并上奏要求兼管交广，任命郗僧施为南蛮校尉，毛修之为南郡太守。
刘裕一一照允，将军胡藩说：“公以为刘将军会一直屈服于你吗？”刘裕沉思半晌，才问道：“什么意思？”胡藩回答说：“公统领百万雄师，战必胜，攻必取，刘毅原是自愧不如；但如果谈及文才，一谈一咏，刘毅却自命为豪雄。最近，有许多文士争相归附他，我担心刘毅未必甘心一直屈居于公之下。”刘裕微笑着说：“我与刘毅同心协力规复朝廷，他有功无过，我怎么能无故陷害他？”胡藩默然退去。
刘裕因刘毅的堂弟刘藩讨逆有功，提拔刘藩为兖州刺史，令他镇守广陵。不久，刘毅身患疾病，郗僧施便劝他上奏，请求调任刘藩为荆州副帅，刘毅当即照做。刘裕这才有些提防刘毅，假意允准刘毅的请求，召刘藩入朝。刘藩自广陵进入京都，刚到宫阙门外，便被逮入大牢。刘裕又向晋安帝诬告说：“刘毅、刘藩两兄弟与仆射谢混图谋不轨，请陛下立即下令赐死谢混、刘藩，讨伐刘毅！”晋安帝不经调查便下诏允准。刘裕立刻召集各军，准备西征。
刘裕任命司马休之为荆州刺史，令他随同前往，并令参军王镇恶、龙骧，将军蒯恩率领前队军士，袭击江陵。王镇恶率领一百多艘战船昼夜兼程，打着刘藩的旗号，直达豫章口。荆州人还没收到刘藩的死讯，以为是刘藩西来，丝毫没有防备。王镇恶舍舟登岸，径直奔往江陵城。刘毅探悉实情，当即下令关闭城门，谁知城门还没来得及关上，兵士还没披上铠甲，王镇恶已闯入城中，全城顿时鼎沸。刘毅率数百亲兵杀出城去，到佛寺投宿，寺僧不肯收纳他。无奈之下，刘毅自缢身亡。王镇恶搜到刘毅的尸首，将他的头颅砍下示众，并杀掉他的族人。
过了几天，刘裕军抵达江陵，杀死郗僧施，赦免毛修之，又调整了赋税，并抚慰人心，荆民大悦。荆州刺史司马休之上任，刘裕立即率大军返回京师。
西行时，刘裕曾令豫州刺史诸葛长民监管太尉军府，处理内部事务，又任命刘穆之为建威将军，辅佐诸葛长民。诸葛长民听说刘毅被杀，便私下对亲属说：“昨天杀彭越，今天斩韩信，恐怕我们也将大祸临头了！”诸葛长民的弟弟诸葛黎民说：“刘氏灭亡，诸葛氏怎么可能幸免于难？我们最好趁刘裕还没回来，赶紧起事！”诸葛长民犹豫不决，偷偷问刘穆之说：“有人说太尉对我不满，他为什么对我不满呢？”刘穆之说：“刘公远征，将家人托付给你照顾，如果他猜忌你的话，怎么会把家人托付给你？”
诸葛长民还是不放心，又致信冀州刺史刘敬宣，劝他共谋富贵。刘敬宣竟然将信件交给刘裕，刘裕随即放出消息，说将抵达京都。诸葛长民于是天天出城恭候，却不见刘裕回来。不料，刘裕半夜入京，回到府第，除了刘穆之外，无人知晓。第二天天刚亮，刘裕就升堂处理京中之事，诸葛长民这才得到消息，惊慌地赶来谒见刘裕。刘裕忙下堂迎接诸葛长民，并喝退堂上其他的人，与诸葛长民握手言欢。诸葛长民渐渐放松警惕，刚想告辞，帐后突然窜出一名壮士，一把抓住他，把他勒死了。诸葛长民的弟弟诸葛黎民、诸葛幼民以及堂弟诸葛秀之相继被斩首。
当时，京都流传一句话：“别嚣张，小心把你交给丁旿。”为什么京都会流传这么一句话呢？原来，刘裕府中埋伏着的壮士叫丁旿。勒死诸葛长民，击毙善斗的诸葛黎民，都是丁旿。众人畏惧他的强悍，所以才有这句话。
刘裕灭掉诸葛氏后，任命朱龄石为益州刺史，令他与宁朔将军臧熹、河间太守蒯恩、下邳太守刘钟率两万大军讨伐西蜀。当时许多人都说朱龄石威望太浅，难当重任，刘裕却力排众议说：“龄石文武全才，此去必能成功。你们要是不信，以后便知！”当下召来朱龄石，和他密谈了几句，又交给他一封锦函，上面写着：“到了白帝城再打开”。朱龄石随即出都，逆江西行。各位将领也不知道朱龄石究竟怎么进攻，只是一路跟着他晓行夜宿。到了白帝城，朱龄石才打开锦函，拿出信函，只见上面写着：
众军从外水攻取成都，臧熹从中水攻打广汉，老弱兵士乘高舰从内水前往黄虎，全军速战速决，违令者斩！
原来，从前刘敬宣讨伐谯纵时，取道黄虎，结果无功而返。此次，刘裕令众军取道外水，是吸取上次的教训。又怕谯纵预料到，所以刘裕特意令朱龄石派老弱士兵走内水，作为疑兵，牵制敌人；又令臧熹从中水进军，无非也是分散敌军的兵力。蜀王谯纵果然怀疑晋军仍然取道黄虎，急忙派谯道福驻守涪城，严防内水。那时，朱龄石已自外水趋往平模，距成都城只有两百里。谯纵得到情报后，忙派秦州刺史侯晖、尚书仆射谯诜率一万多名贼众驻守在平模对岸，筑城据守。
当时正值盛夏，赤日炎炎。朱龄石有些踌躇，对刘钟说：“现在天气这么热，贼众据险自固，我军不容易攻入。我想先养精蓄锐，再伺机发兵，你认为怎么样？”刘钟回答道：“这就错了！我们专门派老弱士兵从内水进军，迷惑敌人，使得谯道福驻守涪城。侯晖等人虽然前来抵抗，但十分惊慌，我军如果趁他们惊疑未定时全力进攻，相信一定能够取胜。平模一被攻克，我军乘胜杀过去，谯纵自然守不住成都。相反，如果我军就此裹足不前，反而会暴露我军的虚实。一旦谯纵调谯道福军赶来援应，我军既不能进，又不能退，师衰食绝，两万人都将成为蜀虏！”朱龄石惊愕道：“幸亏你点醒我，我差点误了大事！”随即麾兵齐进，才半天就拿下平模。臧熹也从中水趋入，一路过关斩将，占据广汉。两军会师，直逼成都，势如破竹。
谯纵接连收到兵败的消息，吓得魂飞天外，急忙弃城出逃。他十五岁的女儿哭着劝他说：“逃跑也难免一死，只能自取其辱，不如到先人墓前，一死了事。”谯纵不听，拜辞先人墓，掉头就走了。他的女儿竟撞死在墓旁。谯道福听说平模失守，忙从涪城回军救援，途中与谯纵相遇，见到谯纵狼狈的模样，不禁愤恨地说道：“你怎么能这么轻易放弃好不容易才建立起来的功业？人生总有一死，有什么好畏怯的？”随即拔剑掷向谯纵，正中马鞍。谯纵慌忙逃避，后来见身边的侍卫都已经离散，只好解带自缢。王志斩下他的首级，献给了朱龄石。
谯道福犒赏军士，打算背水一战，可是军士得了赏银，仍然散去。谯道福孑身远逃，被当地人送到朱龄石军前，斩首示众。入城后，朱龄石只杀了谯纵的亲属，其他人一概不问罪。捷报传到京城，晋廷令朱龄石监管梁、秦州六郡军事，赐封他为丰城县侯爵。