兴平元年（公元194年），正当曹操讨伐陶谦时，张邈和陈宫等乘曹操外征徐州，秘密迎接吕布来担任兖州牧。一时之间，兖州属下的郡、县全都响应吕布，只有鄄城、范县、东阿县没有动摇。
曹操听说后方吃紧，赶忙率军撤回。曹军返回的路线是从郯县直接北归，曹洪率领先头部队首先赶到东平（疑为东阿之误）、范县，在当地筹措军粮，为下一步的反攻做准备。当曹操率领大军越过亢父（今山东省济宁市南）、泰山险道、顺利回到鄄城后，说道∶“吕布一下子就得到了一个州，却没有切断亢父、泰山险道，依托险阻截击我军，反而盘踞在濮阳，由此判断他不可能有什么大的作为。”遂率军对吕布发起了进攻。《战国策》中苏秦所谓“亢父之险，车不得方轨，骑不得比行”，即指亢父、泰山险道，为曹操从徐州返回的必由之路。
吕布在濮阳以西四五十里有一处营垒，曹操趁夜偷袭，经过一夜激战，到黎明时分曹军攻破了营垒。正当曹军打扫战场时，吕布亲自率军赶到了战场，从三面向疲惫不堪的曹军发起了猛攻。当时，吕布亲自冲到前面，两军从凌晨一直打到下午，前后激战了数十回合，不分胜负。危急时刻，曹操招募敢死队抵挡敌人的冲锋，司马典韦第一个站出来应募。
典韦率领数十名应募的敢死队员，全部穿上双层铠甲，丢掉盾牌，手中只拿长矛、撩戟（类似投枪的兵器）。当时，曹军西面情况紧急，典韦率领敢死队抵挡，吕布军弓弩齐射，顿时箭如雨下，但典韦看都不看，对众人说∶“敌人冲到十步时再告诉我!”敢死队员们说∶“已经十步了！”典韦又说∶“五步再说！”敢死队员们心慌了，赶忙说∶“冲上来了！”典韦听罢，手持十几只撩戟，大吼一声，突然从地上一跃而起，杀入敌阵，所遇的敌人无不应声倒毙，吕布军纷纷后退。正巧天色已黑，曹操这才得以撤出战场。回到军营后，曹操当即晋升典韦为都尉，率领数百亲兵充当曹操的贴身卫士。
濮阳城内的大姓田氏答应作为曹操的内应，偷偷打开了濮阳城门，引曹军入城。曹军攻入城内后，烧毁了东门，表示决一死战，绝不后退，可是，吕布的军队作战十分顽强，在曹军冲入城内后，并没有慌乱，而是组织起了有效的反攻。吕布的骑兵先朝青州兵发起进攻，青州兵溃败，引起曹军大乱。吕布的骑兵追上了曹操，却不认识他，问道“曹操逃到哪了”曹操随便一指，说“骑着那匹黄马逃走的就是。”吕布的骑兵遂丢下曹操，追赶那位骑黄马的人去了。曹操骑着马冲入火海，却被摔下马来，被火烧了左手掌，司马楼异搀扶曹操上马，保护着一同逃出了城外。曹操尚未回到军营时，军中谣言四起，都非常担忧。回到营中后，曹操强忍着伤痛，亲自到各营巡视，稳定军心，下令军中加紧修造攻城器具，并立即组织反攻，但依然无法攻破濮阳。
就这样，双方在濮阳城下相持了一百多天，当时，发生了严重的蝗灾，百姓非常饥饿，双方的军粮全都吃光了，遂各自率军离开了濮阳。
兴平元年（公元194年）九月，曹操回到鄄城。濮阳背靠袁绍，前面又是鄄城，腹背受敌，因此，吕布决定离开濮阳，来到鄄城东南的乘氏（今山东省巨野县西南），被当地人李进击破，又向东驻扎在山阳（今山东省金乡县）。吕布向兖州东南发展，主要是为了摆脱不利的战略态势，背靠与曹操为敌的徐州，可以解除后顾之忧。
十月，曹操离开鄄城，率军来到东阿。袁绍派人前来说服曹操，表示与曹操联合，但提出一个条件，那就是让曹操把自己的家眷送到邺城。袁绍的话说得很客气，但曹操当然知道袁绍的意思，一旦曹操把家眷送到邺城，就等于成了袁绍的人质，而曹操也就成了袁绍的部下，再也没有独立发展的机会了。当时，曹操刚刚丢掉兖州，军粮也已经吃尽，几乎到了山穷水尽的地步，打算同意。正巧程昱从外地出差回来汇报，得知这个消息后，引古喻今，力劝曹操坚持下去，这才打消了曹操投靠袁绍的打算。
兴平元年这一年，从四月到七月，没有下一滴雨，天下发生大饥荒，由于无力养活这么多军队，曹操无奈，只好遣散新招募的士兵。
此时，是曹操最为艰难的时刻，但天灾对每个人都是平等的，大灾之下，吕布也是如此，从某种意义上说，这场突如其来的天灾对骁勇善战的吕布军队来说更具毁灭性，这是因为，在曹吕交战时，曹操的军队刚刚东征徐州，又在自己的地盘上作战，曹操收编的青州黄巾军未经严格的训练，作战能力与吕布军相比并不强，而这场天灾却让曹军与吕布军回到同一个起跑线上，从这个意义上说，这未必不是上天对曹操的眷顾。至于曹操在此期间的作为，除了交代程昱建议他拒绝了袁绍的要求之外，再无其他，其间，曹操是如何渡过难关的？史书语焉不详，不过，《文选·袁绍檄豫州文》李注引谢承《后汉书》却记载袁绍出于怜悯之情，分给他五千人马，曹操就凭借这五千人马（可能还有自己的残余军队），东山再起，打败了同样在饥饿线上挣扎的吕布，重新夺回了兖州。
正史可能是出于对曹操的回护，不愿让我们知道袁绍曾经是曹操的救命恩人，才有意漏掉了这一历史事实，这可能才是历史的本来面目。
曹操担任兖州牧后将治所迁到了鄄城（今山东省鄄城县）。整个兖州的布局为西南东北走向∶陈留郡在最西南，中部三个郡自北而南分别是东郡、济阴郡确实存在舞弊现象，遂将侯汶杖打五十，饥民也都得以存活下来。和山阳郡，再往东是任城国、泰山郡，最东北为济北郡。这八个郡国只有三个城池没有背叛曹操，可见曹操在兖州是很不得人心的，而这三个没有背叛曹操的鄄城、范和东阿又都属于东郡，这与曹操担任东郡太守时打下的基础密不可分，至于兖州下余郡县均已背叛∶张邈占据陈留郡，吕布占据山阳郡，并开始蚕食周边各郡。
曹操的东阿、范县、鄄城自东向西一字排开，吕布撤离濮阳后，在三城西北的濮阳等地已没有吕布势力，曹操要想收复兖州，只需从三城向南、向西打。兴平二年（公元195年）春，得到袁绍资助的曹操首先向距离鄄城最近、在鄄城以南的定陶发起了进攻。投靠吕布的济阴太守吴资退守定陶的南城，曹军没有攻下。吕布闻讯，即从东面的山阳郡治所昌邑率军救援，曹操采取围城打援之法，迎头痛击，将吕布的援军击败，随后，曹军似乎已逐渐收复了兖州境内的各座城池。
曹仁率军进攻句阳（济阴郡属县，在今山东省菏泽市以北三十里），生擒吕布部将刘何。在此前后，曹洪也随大军进攻济阴郡、山阳郡，又向西进攻河南尹的中牟县（今河南省中牟县）、阳武县（今河南省原阳县）、京县（今河南省荥阳市）、密县（今河南省新密市）十余县，全部攻克。曹操命令曹洪进攻河南尹所属四县，用意可能在于∶一、阻击可能来自河内张杨对吕布的增援；二、切断吕布西逃之路；三、震慑豫州刺史郭贡。
吕布部将薛兰、李封驻扎在巨野（在鄄城东南、定陶东北）。《新唐书·宰相世系表三下》“薛姓条”记载∶“兖州别驾兰为曹操所杀。子永，字茂长，从蜀先主入蜀，为蜀郡太守。永生齐，字夷甫，巴、蜀二郡太守，蜀亡，率户五千降魏，拜光禄大夫，徙河东汾阴，世号蜀薛。”河东蜀薛在南北朝、隋唐时期显赫一时，曾出了薛安都、薛仁贵等名将。
在消除了西线隐患之后，曹操又放心大胆地转攻薛兰、李封所部。吕布率军前来救援，再次被曹操击败，曹军遂攻克巨野，斩杀了薛兰、李封二人。曹操将大本营设在乘氏（今山东省巨野县西南）。当时，刘备刚刚接管徐州，曹操打算丢下眼前的吕布，趁刘备立足未稳，先夺取徐州，再回过头来进攻吕布。被荀彧反对后，曹操这才打消了原计划。
吕布从东缗（今山东省金乡县东北）出动，与陈宫的军队会合，二人共有一万多军队，向乘氏的曹操大本营发起了一次反攻。当时，曹操的士兵们全都分散到农村抢收小麦去了，留守部队不足一千人，军营防御工事也不到位，局势相当危急。曹操命令随军妇女全部登上城墙防守，自己率领全部兵力出战。在曹军西面有一条大堤，大堤以南林木幽深。吕布担心曹操在那里埋伏有伏兵，遂率军驻扎在十几里开外。第二天，吕布再次率军前来，曹操下令将一半军队埋伏在大堤之内，另外一半则在大堤之外列下阵势。吕布率军冲了上来，曹操这才下令轻装部队上前挑战，双方交手后，曹操一声令下，伏兵突然从长堤内出来，向吕布军发起了猛烈的进攻。吕布军毫无防备，遂被打得大败，曹军缴获了吕布军的鼓车，一直追杀到吕布军营才折返。
当晚，吕布趁夜悄悄撤退了。
乘氏之战后，曹操再次率军进攻定陶，并将其攻克，又分兵平定了兖州各县。吕布、张邈逃奔徐州，投靠了刘备，张邈的弟弟张超保护着张邈家眷驻扎在雍丘（今河南省杞县），到了这一年（兴平二年）的八月，曹操率军包围了雍丘；十月，曹操接到长安朝廷正式任命其为兖州牧的委任状。张邈亲自前往袁术那里求救，为其部下所杀。十二月，雍丘被曹军攻陷，张超自杀，张邈的三族全部被曹操下令诛杀。
至此，经过一年多的奋战，曹操终于平定了兖州全境，曹军又乘胜南下，将豫州的陈郡（今河南省淮阳县）也占领了。