初平二年（191年）的秋天，以于毒、白绕、畦固为首的黑山农民军，开始向冀州的心脏邺城推进，并有渡过黄河南攻兖州的动向。而这时青州的黄巾军一百多万人，因受到袁绍所委派的青州刺史臧洪的军事压力，也正分两路向河北移动，有与河北的黑山军会师之势。
如果河北的黑山军渡黄河而南，或青州的黄巾军渡黄河而北，两支数近百万的大军一旦会师，黄河中下游的力量对比就会引起急而深刻的变化。这样，关东州郡尽管充满内部矛盾还是要集中力量来对付农民军。
袁绍一方面要用堵击或拦截的方法来破坏农民军两路会师的计划；一方面又想利用这一时机，把自己的势力扩展到兖州，使青、兖、冀三州联系起来这样，黄河中下游就全部受他的控制了。要完成这一任务，不得不借重曹操。
于是袁绍以东郡太守王肱不能抵抗黑山农民军为借口，派曹操引兵进入东郡，围攻黑山军。在曹操刚一击溃以白绕为首的黑山军于濮阳（今河南濮阳南）之后，袁绍就以盟主的资格，发表曹操担任东郡太守的职位，袁绍此时满以为自己的势力范围从此可以扩大到兖州地区了。
经过对农民军疯狂地镇压和扫荡以后，到了初平三年（192年）的春天，曹操才把黄河以南的黑山军基本肃清。可是就在同年的夏天，青州的黄巾军却因渡河北上受阻，转而把主力向兖州推进。
曹操
这一支农民军的主力进入兖州以后，首先攻下了任城（今山东济宁市东南），杀死任城相郑遂；接着在东平（今山东东平）附近，击溃了兖州主力军兖州刺史刘岱的部队，在阵上斩杀刘岱并继续向寿张（今山东东平西南）方向移动。充州刺史刘岱阵亡，州中无主，济北（国都卢，今山东长清南）相鲍信和兖州治中万潜等和曹操取得联络，推曹操出任兖州牧。曹操接受兖州牧名义之后，即与鲍信联军堵击农民军于寿张东郊。经过昼夜苦战，农民军虽然阵斩鲍信，并几乎击垮曹操的军队，但农民军亦因损失太重，不得不向济北方向撤退。
曹操纵兵追击，到了这一年的十二月，他终于把青州黄巾军主力击溃，收编降附男女百余万口，得降兵三十余万。曹操就从收编过来的黄巾军中选拔精锐，来充实并扩大自己的队伍，当时称这支兵为“青州兵”。这支青州兵以后在曹操转战中原的统一战争中曾起过很大的作用。
曹操刚把青州黄巾军打败，他在兖州的统治地位还来不及进一步巩固。长安的汉政府由于兖州刺史刘岱阵亡，就任命一个叫金尚的为兖州刺史，令其赶来兖州就任。曹操得到这个消息，预先派兵在兖州边界迎击，金尚只得投奔南阳袁术。
袁术是袁绍的弟弟，是嫡出；袁绍却是庶出，其父袁逢又把袁绍出继给二兄袁成。当袁绍据有青冀二州的时候袁术也据有户口数百万，手工业商业都比较发达的南阳郡。袁术野心大，想做皇帝。他看不起袁绍，认为哀绍是他家“婢使”之子，对袁绍充当关东牧守的盟主非常不服气，兄弟之间关系很紧张。袁术曾远交幽州的公孙瓒，企图颠覆袁绍在河北的统治势力，袁绍也联络荆州的刘表来牵制袁术。
袁术
初平三年（192年）冬天，距离曹操击降青州黄巾军不满二十天，袁术就和公孙瓒遥遥配合，开始向曹操和袁绍进攻。同年的年底，龙凑（在今山东平原境内，古黄河津渡）一役，袁绍击溃了公孙瓒的来犯部队。第二年正月，袁术进军陈留，与曹操作战正处于胶着状态的时候，荆州牧刘表从襄阳进逼袁术的根据地南阳，并切断了袁术的粮道，由此袁术主力不战自溃，向襄邑（今河南睢县西）、宁陵（今河南宁陵东南）一带退却。
从此袁术失掉南阳，退到淮北，又从淮北退到淮南，以寿春（今安徽寿县）为根据地。袁术退到淮南以后，西面受到荆州牧刘表的威胁，东北面又不可能向徐州发展，于是想利用江东籍的将领孙策来经略大江以南，这引起了以后孙策的渡江和拓定江南，给东吴政权奠定了基业。
曹操于初平四年（193年）春天把袁术击退，在同年秋天，就发动进攻徐州（治下邳，今江苏睢宁西北）牧陶谦的战争。
曹操进攻徐州，有两个原因。第一个原因，当时曹操是依附袁绍的，可是陶谦却和公孙瓒结成联盟，与袁绍为敌。当公孙瓒进攻袁绍的时候，陶谦还曾出兵配合公孙瓒进攻袁绍。因此，袁绍击退公孙瓒、曹操击溃袁术之后，他们就必然要把兵锋转向徐州。
但是那时河北地区的黑山农民军于毒部又活跃起来，一度进入冀州的心脏邺城，袁绍忙于镇压黑山农民军，无暇远略，所以进攻陶谦的责任，就落在曹操一个人身上。
第二个原因，曹操的父亲曹嵩本来居住在故乡谯县，山东牧守兵起，他从谯县避难至琅邪（国都开阳，今山东临沂北）。曹操出任兖州牧后，想把父亲接到任所。曹嵩走到兖州属郡泰山界内华县（今山东费县东北）、费县（今山东费县西北）界内，遭到陶谦的部将张闿等的袭击，曹嵩及其次子曹德全家数十口都被杀死，一百多车财物也被掠一空。所以曹操攻入徐州，志在复仇。
曹操攻入徐州境内，接连攻下彭城（今江苏徐州市）以北的十多座城市，屠杀人民数万口，这带破坏得“鸡犬亦尽，墟邑无复行人”。曹操在徐州屠杀了一阵以后，军食亦尽，到兴平元年（194年）春天退回兖州。
陶谦
曹操将军队略加整补，后方也略加部署之后，就在同年的夏天，再度进攻徐州，还是和上次那样，“所过多所残戮”，最后还想进攻陶谦所驻的下邳，由于陶谦的堵击，同时兖州境内，正酝酿着一次巨大的政变，陈留太守张邈联络驻屯东郡的曹操部将陈宫，迎吕布出任兖州牧，共拒曹操，这就迫使曹操不得不迅速把自己军队从徐州撤回来了。
吕布杀了董卓以后，王允并没有怎样重用他。董卓部将进攻王允，围攻长安城时，吕布率百余骑自长安逃出，由武关（今陕西商州东）至南阳，想投奔袁术，但为袁术拒绝。他又投奔袁绍，又遭袁绍猜忌，乃改投张杨（故何进部将）于河内。途中经过陈留，和张邈“把手共誓”。
自从曹操出任兖州牧以后，张邈和曹操之间的关系开始恶化，这时张邈和陈宫联合，派兵迎吕布进驻濮阳（今河南濮阳南，本为东郡治所，曹操做东郡太守，移东郡治东武阳，今山东莘县西南），推布为兖州牧。
由于张邈和陈宫在兖州陈留、东郡等地区拥有一定的地方势力，因此他们出来反对曹操，立时“郡县响应”。只有曹操的驻地鄄城（今山东鄄城北）和东郡的两个属县范（今河南范县东南）、东阿（今山东阳谷东北）两城在曹军坚守中。这时曹操抽调了绝大兵力去攻打徐州、“留守兵少”，后方非常空虚，而兖州（鄄城）城内的督将大吏，多与张邈、陈宫通谋”，对曹操说来形势是极危险的。
曹操自出任兖州牧之后，已把东郡太守让给自己最亲信的将领夏侯惇来担任。到曹操去攻打徐州时，又把兖州后方的留守事务交给荀彧去处理。荀彧赶忙把夏侯惇的军队从东郡调回鄄城，连夜杀督将大吏谋叛迎吕布者数十人，把兖州的政治中心鄄城稳定了下来。同时又派东阿人程昱前往范、东阿两城，鼓励当地官吏“拒城坚守”。吕布进攻鄄城不克，西屯濮阳。曹操便回军攻打濮阳，濮阳大姓田氏在城内响应曹操，曹操亲率战士入城，可是巷战失利，险些被吕布的骑兵抓住。结果冒着火焰，从东门逃出，左手掌被火烧伤。
曹操和吕布交战了百多天。战斗的持续进行，使得农民无法从事生产。这年夏天，蝗虫又特别多，发生了大饥荒,“百姓大饿”。吕布也是非常缺乏军粮，只得退兵。九月间曹操回到鄄城，吕布也退屯山阳郡治昌邑（今山东金乡西北）。曹操用了一年多时间，才把兖州的郡县陆续收复。到了兴平二年（195年）的夏天，经过巨野（今山东巨野南）会战，曹操终于击败了吕布，使吕布不得不向徐州方向逃奔。张邈随吕布南奔，后来为其部下所杀。
这样，曹操在兖州的统治地位总算渐渐稳固下来。当曹操同吕布作战相持不下之际，袁绍曾派人劝说曹操把家属遣送到邺城居住，实际上就是叫曹操对袁绍“称臣纳质”。
曹操的谋臣程昱等人表示反对，曹操也没有答应。从这一桩事可以看出，一方面当时“袁曹方睦”，他们之间的关系还算和睦；另一方面随着时间的推移，形势的进展，袁曹之间的矛盾也快要表面化了。
