献帝初平三年（192年）春，曹操在顿丘驻军，于毒等进攻东武阳。此时曹操却命军队西行入山，向于毒等的大本营进攻。曹操部下将领都请求援救东武阳，曹操说：“把我们西行的消息透露给叛贼，他们如果回来救援，东武阳的包围将不救自解；如果他们不回来，我们定会将他们的营寨攻下，而他们肯定不能攻下东武阳。”于是，率军出发。于毒听此消息后，果真放弃东武阳回救大营，曹操乘机进攻内黄，打败黑山军眭固部及南匈奴单于于夫罗。
献帝初平二年（191年），青州军大举进攻渤海郡，在东光遭到公孙瓒的攻击，青州军因此而失败，伤亡惨重。次年，青州军向兖州进军，先攻下了任城（今山东济宁），杀死任城相郑遂，接着又进攻东平。兖州刺史刘岱准备率兵还击，济北相鲍信劝阻他说：“如今青州军力量强大，拥兵百万之多，百姓都十分恐慌，士兵也无斗志，不可与他们交战。但是，青州军没有军需物资，坚持不了多长时间，我们不如暂且保存实力，固守城池，敌军求战不得，攻城又不下，时间一长他们的力量定会削弱。到那时，再挑选精锐部队，镇守关口要塞，定可将他们击败。”刘岱不听其言，率军和青州军交战，结果被青州军杀死，兖州一时没人主持事务。
曹操的部将陈宫对曹操说：“刘岱已死，州中无主，断绝了与朝廷的关系，我想说服州中的主要官员，同意由您主持州中事务。以此为资本，进而夺取天下，这可是霸王之业。”接下来，陈宫对兖州的主要官员说：“如今天下分裂而州中无人主持事务，曹操为一代英才，如能迎接他做州牧，必然能使百姓安定。”在鲍信的帮助下，陈宫终于说服了兖州的主要官员。于是，曹操兼任了兖州牧。
曹操到任之后，便率军前往寿张东攻打青州黄巾军。黄巾军勇敢精悍，曹操因势单力薄，没能取胜。鲍信也被黄巾军杀死。鲍信是曹操的旧友，鲍信死后，曹操异常伤心，下令悬赏寻找鲍信的尸体，但没能找到，只好让人刻了鲍信的木像。下葬之时，曹操大哭不止。黄巾军与曹操经过昼夜激战，中了曹操埋伏，损失惨重，也退出兖州，向济北撤退，曹操却紧追不舍。黄巾军给曹操写信说：“你过去在济南，毁坏神坛，这同我们黄巾军信奉的太乙是相同的。你像是懂道的人，现在怎么迷惑了。汉命已尽，黄家当立，这是天命，不是你所能阻止得了的。”曹操见信之后，一面大声斥骂，写信给黄巾军，指出投降的出路；一面设伏兵，与黄巾军昼夜激战，终于将黄巾军击败，俘获兵士三十余万人，男女人口百余万人。曹操挑选其中精锐之士，组成军队，称为“青州兵”。
之后，曹操在兖州刚刚立足，就遭到袁术的攻击。献帝初平四年（193年）初，袁术受到刘表的威胁，率军进入陈留，移驻封丘。黑山军的一支和南匈奴于夫罗全都归附了袁术。曹操当时驻军于鄄城，率军迎战。正在这时，刘表杀了袁术的部将孙坚，切断了袁术的粮道。曹操乘机击退袁术，袁术被迫退居淮北。曹操打败袁术后，于献帝初平四年（193年）还军定陶（今属山东）。
初平四年（193年）秋，曹操向徐州进兵，为的是向东南扩张其势力。徐州当时是陶谦的势力范围。陶谦字恭祖，丹杨人。他年轻时好学，是位儒生，出任州郡吏，被举为茂才，当上卢氏县令，又被升迁为幽州刺史。后任命为议郎，任车骑将军张温的参军事，被派前去征讨韩遂。正逢徐州黄巾军起义，陶谦就做了徐州刺史，征讨黄巾军，将黄巾军打得四处逃散。董卓叛乱后，各州郡都拥兵自重，天子在长安建都，与外界完全断绝联系。陶谦派使者向天子进献，被天子提升为安东将军、徐州刺史，封溧阳侯。陶谦肆意妄为，广陵太守琅琊人赵昱是徐州名士，因为忠诚正义而被他疏远；曹宏等奸谗小人，却反而受重用。于是刑罚、政事弊端开始出现，善良的人基本上都被他迫害，社会由此动荡起来。下邳的阙宣自称为帝，陶谦最初与他联合四处抢掠，后来杀死了阙宣，收编了他的部队。献帝初平四年（193年）夏，曹操之父曹嵩在琅琊避难，曹操派人把他父亲接到兖州来。途中，曹嵩被陶谦部将堵截，曹嵩被杀，一百多车财物被抢走。曹操深恨陶谦，于秋天发动了对徐州的进攻，连续攻克十余城。到达彭城时，与陶谦军展开激战。陶谦战败，退守郯县。
以前京师洛阳一带遭董卓之乱，百姓都向东迁移，大多数投奔到徐州。徐州地区百姓富裕，粮食丰足。曹操攻入徐州，在泗水旁杀了几十万老百姓，泗水为之不流。曹操攻不下郯县，便派兵向南攻克虑县、睢陵、夏丘，所到之处屠戮无数，故城尽为废墟，行人断绝。陶谦向青州刺史田楷请求救援，田楷派平原相刘备率数千士兵前往救援。陶谦又增拨丹阳郡兵士四千名归刘备指挥，任命刘备为豫州刺史，屯兵小沛。这时曹操也因粮草不济，率军退回兖州。
献帝兴平元年（194年）四月，曹操再征陶谦。他派司马荀彧、寿张县令程昱留守鄄城，亲自率领部队出征，一路打到琅琊、东海，返回时，在鄄县以东将刘备的军队击败。陶谦恐惧，想逃回丹阳。这时，兖州境内发生了反对曹操的叛乱。曹操闻讯之后，急忙撤军，力求挽救兖州。
这次叛乱是陈留太守张邈发动的。张邈年轻时，喜好游侠，同曹操、袁绍的关系不错。袁绍当上讨董联军的盟主后，非常傲慢。张邈严厉地批评袁绍，袁绍非常恼怒，命曹操去杀张邈。曹操予以拒绝，说：“张邈是我的好朋友，有什么过错理应宽容，今天下尚未安定，怎能自相残杀呢？”曹操第一次攻打陶谦时，决意死战，于是告诉家人说：“如果我不能生还，你们就去投靠张邈。”后来曹操胜利归来见到张邈，两人相对落泪。然而，自曹操出任兖州牧之后，势力不断壮大，心里惴惴不安。尤其是前任九江太守边让曾因讥讽曹操全家惨遭杀害后，张邈害怕终有一天被曹操所灭。边让声望很高，才华出众，他的被杀使兖州地区的士大夫都感到恐惧。陈宫性情直率刚烈，心里也疑虑不安，就与从事中郎许汜、王楷及张邈的弟弟张超一起策划背叛曹操。陈宫对张邈说：“如今天下分裂，豪杰纷纷崛起，您拥有广阔的土地、大量的人口，又处于四方必争的要冲之地，完全有能力成为人中豪杰，为何反而受制于他，这岂不是太鄙陋了吗？曹操如今率军东征，州中一定空虚，吕布是个能征善战的勇士，应当将他请来，一同主持兖州事务，等待时局变化，这正是您施展才能的良机。”张邈听从了陈宫的建议。
以前曾参加过讨伐董卓之战的陈留太守和曹操部将陈宫都对曹操不满，遂反叛曹操，迎吕布为兖州牧。当时只有鄄城（今属山东）和东郡的范（今山东范县东南）、东阿（今山东阳谷东北）两县在曹操的掌握之中，分别由司马荀彧和寿张令程昱、东郡太守夏侯惇等坚守，形势非常危急。曹操从徐州赶回，获悉吕布屯于濮阳，遂进军围攻濮阳。
曹操说：“吕布得一州，却不能占领东平，截断亢父（今山东济宁南）乘机袭击我，而是退驻濮阳，我料定他是没有任何作为了。”四月，曹操率领军队围攻濮阳。曹操将吕布的一支部队在濮阳以西击败，还未来得及回撤，吕布赶来援救，双方遂展开激战，从早打到晚，不分胜负。曹操为打破僵局，招募壮士袭击敌阵。司马典韦带领壮士冲到阵前。吕布命令弓弩手放箭，一时箭如雨下。典韦很镇定，根本不放在眼里，对壮士们说：“等敌人离我们还有十步远的时候再告诉我。”壮士们说：“已经十步了。”他又说：“离我们还有五步的时候再告诉我。”说话之间，吕布的军队已来到眼前，壮士们惊呼：“敌人现在到了！”典韦这时才持戟大喊而起，带领壮士冲上前去。他们英勇无比，吕布军队仓皇后退。这时天黑下来，曹操率军回营。典韦立下大功，曹操提升他为都尉，命他率领亲兵，负责大帐左右的警卫。
不久，曹操再次攻打濮阳时，在濮阳大姓田氏的帮助下，曹操得以进入城内，并烧毁城东门，表示不再退回。经过与吕布军队交战，曹军大败。吕布的骑兵捉住了曹操，但他们不认识曹操，问道：“曹操在哪里？”曹操说：“前面骑黄马逃走的那个就是。”吕布的骑兵一听，将曹操释放，追赶骑黄马的人去了。曹操从东门的大火中逃脱。回到营中，他亲自慰劳军队，鼓舞将士士气，命令尽快赶制攻城器具，再度进攻濮阳。曹操与吕布激战一百多天不分胜负。
吕布粮尽，曹操也因军队乏粮，双方都各自退兵。九月，曹操回到鄄城，吕布率领军队到达乘氏县。乘氏县人李进将吕布击败，吕布无奈向东退到山阳。
曹操到这年冬天来到东阿县。袁绍想联合曹操，条件是曹操的家眷必须居住在邺城，实际上袁绍是凭自己雄厚实力逼迫曹操送人质。此时，曹操已丧失了兖州的大部分地区，军粮即将吃完，正处在困难之时，想要答应袁绍的建议。程昱却极力反对曹操这样做，他说：“我认为您这是临事畏惧的表现，如果不是，您为何考虑得这样不周全！袁绍的野心是吞并天下，但以他的智谋这个愿望是不能实现的，难道您愿意臣服于他吗？以您龙虎之威，能做当年刘邦手下的韩信、彭越吗？兖州现在虽然残破不堪，但您还控制着三座城，战士万余人，以将军的神武，荀彧、程昱等人的帮助，霸王之业一定能实现。希望您慎重考虑再作决定！”曹操采纳了程昱的意见，没有将家眷送往邺城。
程昱，字仲德，东郡东阿县人，身长八尺三寸，胡须长得特别美。黄巾兵起义时，县丞王度起兵响应，烧毁仓库。县令仓皇翻墙逃走，官吏百姓都背负老幼向东逃奔至渠丘山。程昱遣人侦察王度的情况，得知王度等人只得到一座空城而已，不能据守，于是在离城西四五里的地方驻扎。程昱对县中大族薛房等人说：“现在王度等人已经得到城郭却不能据守，其成败大事就已经很清楚了。他们只不过想要抢掠财物，并没有扩充实力、训练军队的志向。我们现在为何不返回城中守城？城墙既高且厚，并且城中积存的粮食很多，现在如果回去请求县令帮忙一同坚守，王度定不能坚持很久，那时便可一攻而破。”薛房等人认为他说得有理，但吏役百姓却不肯听从他的意见，说：“王度在西边，我们只有向东去。”程昱对薛房说：“和愚民不可商议大事。”于是秘密派遣几人到东山上高举幡旗，以使薛房等人能看到，并大喊说：“王度已来了！”随即下山直奔城内，吏民也奔走跟随，去找县令，共同守城。不久，王度等人来攻城，久攻不下后撤离。程昱率吏民打开城门紧追其后，王度等人被打得落荒而逃。东阿县城因此得以完整保全。
献帝兴平二年（195年）春天，为争夺兖州，曹操再次与吕布交战。正月，曹军在定陶击败吕布。四月，又在巨野击败吕布，并且斩杀吕布部将薛兰等人。此时传来徐州牧陶谦病死的消息，曹操想乘机夺取徐州，回头再攻打吕布。荀彧对曹操说：“从前，汉高祖刘邦保关中，光武帝占据河内，都是先牢牢控制其根据地之后，再图控制天下，进可战胜敌人，退可坚守，所以偶有失败，但仍能完成统一大业。将军原是在兖州起兵，平定山东之乱，百姓没有不心悦诚服的。兖州重地，如今虽已残破，但还易于自保。这正是您的关中、河内，应先巩固兖州。您已打败了李封、薛兰，我们应该乘机派兵收割麦子，节衣缩食，储备粮草，到那时就可以一举打败吕布。徐州如果攻不下来，将军您将去哪里呢？”
曹操采纳了荀彧的意见，打消了东征的念头，命其部下全去收割麦子，留在营中的不足一千人。这时，吕布、陈宫率领万余人前来进攻。曹军形势非常危急，难以守住营寨。曹操决定以计破敌。在营寨西边有一条大堤，南面却是一大片茂密的树林，曹操让一半士兵埋伏在堤后，另一半士兵显露于堤外。当吕布的军队靠近时，曹操命轻装部队前去挑战，双方交战之后，才命令堤后伏兵杀出，步兵、骑兵一齐冲锋，致使吕布大败，吕布军向徐州方向撤退。曹军攻下定陶并平定了其他县城。张邈随同吕布前往徐州，他的弟弟张超带着家属退守雍丘（今河南杞县）。
八月，曹操包围雍丘，至十二月，攻下雍丘，张超自杀。张邈获悉雍丘被围的消息后，想到袁术那里请求援助，在途中却被部下杀死。至此，曹操又重新占领了兖州。这年冬天，朝廷任命曹操为兖州牧。