第二年，青州黄巾军人兖州，先攻下任城(今山东济宁市)，杀死任城相郑遂，接着向东平(今山东东平县东)进军。兖州刺史刘岱截击黄巾军，被黄巾军杀死。这时曹操正准备以东郡为基地，扩充势力。当刘岱死后兖州“州中无主”的消息传来，东郡人陈官为了使曹操占据兖州，去做说客。他对兖州的大小官员说：
现在全国处于动乱之中，州中又处于无主的状态。曹东郡有治世之才，如果由他出任本州牧，一定能够负起阻击黄巾军的任务，并且可以保护本州百姓，使地方得以安宁。①
这时曹操的故友鲍信，也竭力说服大家接受了这个意见。于是鲍信和兖州治中万潜亲自赶到东郡，把曹操迎到兖州，做了兖州牧。曹操时年三十八岁。
兖州东接青州、徐州，西部南部连豫州，北通冀州、幽州，南下江淮，属下有八个郡，辖区包括今山东西南部、河南东部的广大地区。
曹操得到了兖州地盘，而且得到了兖州军队，还得到了兖州有名的谋士程昱(字仲德)。原来刘岱推荐程昱为骑都尉，程昱以有病推辞不就。曹操与程昱长谈后，二人很是投合，曹操任命他为寿张令，他欣然接受了。当程昱准备上任时，乡亲中有人问他说：“你前后的态度为什么相反呀？”他笑而不答。
接着，曹操与鲍信进击黄巾军于寿张(今山东东平县西南)，被黄巾军打败，鲍信被杀死。后来曹操“明设赏罚，承间设奇，昼夜会战”，青州军遭受损失，不得不向济北(今山东济南市长青区南)方向撤退。曹操纵兵追击。青州军给曹操写信说：“你过去在济南，毁坏神坛，这个精神和我们黄巾军之道相同。你似乎是个懂道理的人，但现在怎么迷惑了。汉行已尽，黄家当立，新的天下就要出现，不是你的才力所能阻止得了的……”幻想取得曹操的合作。但曹操是统治阶级的代表，不可能放弃对农民起义军的镇压。他采用武装镇压和诱降相结合的手段，迫使青州军三十万向他投降。曹操从其中挑选精锐五六万人组成一支战斗力很强的队伍，号为“青州兵”。
这期间曹操的武装力量有了很大的发展。曹操出任东郡太守以后，山阳巨野(今山东巨野县)的豪强地主李乾纠合数千家宾客和曹操联军。李乾及其子李整死后，其侄李典就率领宗族、部曲归附曹操。勇将典韦也投到曹操所部夏侯悖的帐下。曹操领兖州牧后，任城地主吕虔也率领一批家兵归附。泰山巨平(今山东泰安市南)人于禁，原为鲍信手下的普通兵士，前来投奔曹操。曹操根据他的才干，提拔他为军司马。
这样一来，曹操手下的战将多了，军队增加了，又有了精锐的“青州兵”，他的武装力量便进一步壮大了。这是曹操在兖州建立根据地的重要凭借。
曹操在兖州刚立住脚，就遭到袁术的进攻。兖州在袁术占据的南阳和袁绍占据的冀州的中间，袁术要向北发展势力，必须首先占领兖州。192年冬，曹操刚击降青州黄巾军不久，袁术和公孙瓒就南北配合，同时向曹操和袁绍进攻。公孙瓒还派部将刘备为平原相，帮助青州刺史田楷、徐州牧陶谦，从东面威胁兖州。这时，曹操表面上继续保持对袁绍的依附关系。年底，袁绍在龙凑(今山东平原县附近)击溃公孙瓒的主力，迫使他逃回幽州。第二年(193年)，曹操在封丘(今河南封丘县西南)等地打败袁术，逼使他离开南阳(这和荆州牧刘表的进逼也有关)，退居九江(郡治寿春，今安徽寿县)。
曹操大败袁术，解除南面的威胁之后，开始向东面的徐州发展势力。
这时徐州牧是陶谦。陶谦(字恭祖)是丹阳人，因参加镇压徐州黄巾军有功，被东汉政府任为徐州刺史。董卓专权时，他没参加关东联军讨伐董卓，被董卓提升为徐州牧。董卓被杀后，陶谦同袁术、公孙瓒联合，与曹操为敌。193年夏，曹操派人到琅玡(今山东临沂市北)接父亲曹嵩来兖州，在途中被陶谦部将张闽截击，曹嵩被杀，一百多车财物被抢。这样，曹操同陶谦的仇恨就更深了。
同年秋，曹操亲率大军，东征陶谦，连下徐州十多个城池，进抵彭城(今江苏徐州市)。陶谦领兵前来会战，被曹操打败，退保郯县(徐州治所，今山东郯城县西南)。曹操攻郯不下，引兵向南攻陷取虑(今江苏睢宁县西南)、夏丘(今安徽泗县)等地。这时，曹操军队的纪律还很差，曹操的复仇心理也很强，“所过多所残戮”。陶谦急忙向青州刺史田楷求救。田楷派平原相刘备率数千人去支援。陶谦推刘备为豫州刺史，给他四千人，命他屯小沛(即沛县，今江苏沛县东)，抵抗曹军。这时曹操“军食亦尽”，便领兵退回兖州。
兴平元年(194年)四月，曹操第二次东征陶谦，大军进入徐州后，连下五城，一直扫荡到琅玡、东海两郡，“所过残灭”。曹操前后“凡杀男女数十万口”，曹操想拿下徐州治所郯县。陶谦和刘备合军在郯县东郊堵击，被曹军打败，陶谦准备逃向丹阳。正在这时，兖州境内发生了反对曹操的叛乱。曹操闻讯，急忙撤军，赶回兖州。
这次叛乱是陈留太守张邈(字孟卓)发动的。张邈本来和曹操的关系很好，曾支持曹操在陈留起兵。关东联军讨伐董卓时，曹操实际上是张邈的部将。曹操代刘岱出任兖州牧以后，地位居于张邈之上，张邈内心便有些不服。虽然曹操对张邈表示充分信任，在第一次东征陶谦时曾对自己家属说：“我如果战死了，你们就去投靠孟卓。”但张邈害怕终有一天会为曹操所灭，“心不自安”。这时张邈手下的陈宫由于曹操将兖州名士边让杀了(因“讥议”曹操)，也产生疑惧，便劝说张邈乘曹操领兵东征内部空虚的时机，迎接在河内的吕布来一起统治兖州。张邈同意了陈宫的计划，派兵劝迎吕布到濮阳来，并推吕布为兖州牧。
张邈和陈宫在兖州统治已十多年，尤其是在陈留郡和东郡，有深厚的潜在势力，因此他们一起来反对曹操，立刻“郡县皆应”。只有兖州治所鄄(音绢，juan)城(今山东鄄城县北)以及东郡的两个属县范和东阿，还在曹操手中。同时，鄄城城内不少将吏也与张邈通谋，形势对曹操来说的确是危险的。这时留守鄄城的苟或，沉着冷静，他一方面派人将张邈叛变的消息通知曹操，一方面派人把驻扎在东郡的大将夏侯悖调回鄄城。在夏侯悖率领本部人马回到鄄城的当夜，就把在城内通敌的将吏数十人杀掉，安定了军心。荀或还派程昱到范和东阿，鼓励当地官兵“拒城坚守”，等待曹操回军。P28-31