东晋建武元年（317年），祖逖北上到了黄河以南地区屯驻在芦洲（今安徽毫县东）。这时，在不远的谯郡（今安徽毫县）等地，有张平和樊雅的两个坞壁。张平，被北中郎将刘演署命为豫州刺史，和祖逖一样的官号。樊雅被刘演署命为谯郡太守。他们分别拥有几千士兵。还统领着董瞻、于武、谢浮等十几个团伙。每个团伙有几百人。加起来，是一支很强的兵力。祖逖先是用友好的方法，派参军殷父去劝说两个坞主，争取和解。但是，张平、樊雅都不想归顺晋朝。殷父劝说时又态度傲慢，带着轻视、侮辱的语气。因此，不仅和谈不成，张平、樊雅还杀了殷父。和平谈判不成，祖逖只好采用强硬的方法解决。双方对垒后，由于祖逖兵力相对弱小，因此，相持一年多，没能分出胜负一继续僵持下去，会延误北伐的时问。为此，祖逖决定智取。他买通了张平的部属谢浮。谢浮用计谋杀了张平，把头献给祖逖。消息传到建康，晋元帝很高兴，为嘉奖祖逖的战功，司马睿派人给他送去一批军粮。但路途遥远，没能运到、接着，祖逖带兵进据太丘（今安徽永城西北）。樊雅听说后，急忙调兵遣将攻打祖逖。他暗中派兵，趁着夜晚偷袭祖逖的大营。敌兵进入祖逖军队的营地后，拔戟大声喊叫，一直杀到祖逖的军帐。一时，军营中一片慌乱。祖逖临危不惧，镇定地指挥左右顽强抵抗。经过都护董昭等人的拼死冲杀，最终打退了樊雅的军队。接着，祖逖率军乘胜追击，包围了谯城。虽曾几次打败樊雅的军队，但是，因为谯城防守严密，又有张平的余部帮助樊雅，一直攻打不下。祖逖又派人向南中郎将王含请求援助。王含答应了祖逖的请求，派参军桓宣领500十兵援助祖逖。桓宣是当时有名的将领，曾经先后几次打败石勒。还曾奉晋元帝司马睿之命，劝说张平、樊雅归顺东晋。张平、樊雅表面上听从桓宣的规劝，臣服于晋朝。但是实际上并没归降。祖逖很赏识和器重桓宣，让他单人匹马，带两名随从，再去说服樊雅。桓宣动之以情，晓之以理，向樊雅申明民族大义，又申说了利害和前途。义正辞严，言语恳切。经过两次反复劝说，樊雅终于被打动了，主动开城门请降。祖逖如愿收复了谯城。桓宣退兵回去。
石勒听说祖逖占据了谯城，十分惊慌。他急忙派侄子、后赵大将石虎带兵包围谯城。王含又派桓宣带兵援助祖逖。石虎听说桓宣来增援，连忙收兵回营，谯城转危为安。占据谯城，这是祖逖自北代以来取得的第一个重大成果。他很高兴，随即上书晋元帝，奏请桓宣作谯国内史，协助自己讨伐那些还没归顺的坞主。
此后的几年里，祖逖的北伐进入了更加重要的阶段，斗争也更加艰苦。稳住谯城以后，祖逖率兵北上，和蓬陂（今河南开封东南）坞主陈川遭遇。陈川本性贪残凶暴，他据守蓬肢，自称宁朔将军、陈留太守。早在祖逖打樊雅时，曾经向陈川请求援助，陈川派他的部将李头带兵援助祖逖。李头打仗勇猛，屡次打败樊雅的军队。有一次，在双方军队交战中，祖逖的军队打了胜仗，缴获了樊雅的一匹骏马。李头很喜欢这匹马，爱不释手。但又不敢开口要。祖逖知道了他的心思，就主动把这匹马送给了李头。李头非常感激他、敬佩他，经常在别人面前称赞祖逖，说：如果能得到祖逖将军这样的人做首领，就是死了，也没有什么遗憾的。陈川听了这些话，既嫉恨祖逖的声望，又气恼部将的不忠，为了杀一儆百，他杀了李头。但是，结果却适得其反，李头被杀后，他的部将冯宠就带着部众跑来归附了祖逖。陈川把这一切怨恨都归结于祖逖。为发泄嫉恨的心绪，他派部将魏硕带着士兵在豫州的各郡大肆抢掠财物，抓获男女壮了。祖逖作为豫州刺史，当然不能放任不管。他派将军卫策在谷水截击魏硕，把他们抢来的车马人物全部夺获，并全都归还原主。而青天严禁自己的将士从中拿任何东西；祖逖的言行，维护了群众的利益，赢得了当地百姓更深的拥戴。
陈川不想忍气吞声，但又害怕祖逖。为了寻找一个靠山，东晋太兴二年（319年），他献出自己驻守的浚仪县（今河南开封），投奔了石勒，和祖逖相对抗。当祖逖派兵打陈川的蓬关的时候，石勒马卜派石虎领兵5万南下，渡过黄河，援助陈川。在战争开始的一段时间，祖逖吃了败仗。后来，他设法避开石虎军队的主力，退兵屯驻在梁国（今河南商丘南）。这时，石勒又派部将桃豹占领蓬关。为保全实力，祖逖率军再后退到淮南（今安徽寿县）。后来，祖逖用奇计大败石虎的军队。石虎大败后，把陈川的5000户部众迁徙回襄国（今河北邢台），留下桃豹等人驻守陈川做城。
东晋太兴二年（320年），祖逖的军队和石勒在陈川故城展开了激烈的争夺。当时，受石勒派遣的桃豹的军队驻守在故城的西台。祖逖派部将韩潜驻守在故城的东台。两军对垒。在同一个大城里，桃豹的士兵放牧从南门进出，而韩潜的士兵开东门出入。双方你来我挡，互有胜负，相持了大约四旬的时间。这是自祖逖北伐以来，继占领谯城之后，和石勒的又一次大的较量。考虑到石勒的军队实力比较强，继续相持下去会延误时间，硬挤一时义没有充分的把握取胜。因此，祖逖决定斗智不斗勇，想办法智取陈川故城。当时，由于经历了汉末以来直到十六国的战乱，北方经济严重凋敝，百姓一贫如洗，经常没饭吃。部队要凑集军粮更难。因此，军营里粮食、给养十分缺乏。祖逖利用石勒的部众求粮心切的心理，设计了一个计谋。
某一大，祖逖让l000多名土兵，带上很多布袋，每个布袋里都装满泥土，装成运粮的队伍，来来往往，一布袋一布袋地往营地里搬，让石勒的军队能看见。同时，祖逖又派一些人，挑着粮食，装出非常劳累的样子，在半路上歇息。困在城里40多天的桃豹，一看见粮食，喜出望外，不顾一切地派人来抢米。那几个挑粮食的人，故意装出很害怕的样子，丢下米担撒腿就跑。桃豹的士兵把东西捡回来一看，全是好米。再看看祖逖军营里一堆堆装得满满的布袋，以为都是粮食。于是，十兵都说祖逖的军队粮食充足，兵强马壮，而他们自己军营中的粮食给养很快就中断了，支撑不了多久。因此，军心动摇，士气低落。正好这时候，石勒派部将刘夜堂，用l000多头驴，驮着粮食给桃豹送来。祖逖听说了，派韩潜、冯铁等人，在浚仪附近的汴水设下埋伏，把石勒送给桃豹的军粮全都截留。
桃豹本来把解决军粮的希望寄托在这些粮食上，听说都被祖逖抢去了，非常绝望，没有再打下去的勇气，丢下浚仪城，在一个漆黑的夜晚，率领全军逃走，退到东燕城（今河南延津北）。祖逖终于以智取胜，用计谋巧妙地占取了浚仪城，取得了自北伐以来的又一次重大胜利。不久，祖逖又乘胜追击，派韩潜进驻在封丘（今河南封丘），形成对东燕城的进逼态势。又让冯铁据守在二台。祖逖自己驻在雍丘（今河南杞县）。同时，多次派军队到处截击石勒的军队，使石勒的屯戍逐渐缩小。
祖逖北代以来，占谯城，夺浚仪，几次大败石勒。黄河以南广大地区的局势大大改观，一些本来就对石勒统治不满的地主也起来公开反抗石勒，并表示要归附晋朝。祖逖充分利用人心归向的有利时机，争取当地地主武装的归顺与合作。当时，比较有影响的坞主，像赵同、上官已、李矩、郭默等，都属于可以团结争取的对象。如河内郡人（今河南沁阳）郭默，在永嘉之乱以后，率领部众结坞自保。他爱抚将士，体贴部众，因此，很多人跑来归附他。还有东郡东阿（今属山东）人魏浚，在洛阳被刘耀打败以后，屯兵洛北，招兵买马，打造兵器，周围的百姓都来投奔他。后来，魏浚在和刘曜的一次大战中不幸战死。这些有识之士，在同难面前不退缩，以不同的方式尽着报国的心力。他们当中，由于种种原因，有的有隔阂，甚至一度火并。其中大多数和祖逖的北伐军也没有什么直接联系。但本质上都是可以争取的对象。为了把这些人团结在自己的名下，增强北伐的实力，祖逖做了大量的排解工作。耐心地说服那些彼此对立的坞主，让他们团结起来，共赴国难。像上面提到的李矩和郭默，本来互相敌对，经常交火。祖逖派人去做他们的工作，申明民族大义，讲清得失祸福。李矩和郭默听了祖逖的规劝，很受感动，不但消除了彼此之间的对立情绪，握手言和，而且感激祖逖的恩德，都来投奔他，接受祖逖的节制。