初平二年（191年），黑山賊于毒、白繞、眭固等率十多萬人攻打魏郡、東郡，東郡太守王肱不能抵御。
曹操引軍入東郡，在濮陽擊破白繞。
因此，袁紹表曹操為東郡太守，治所在東武陽。
初平三年（192年），曹操駐軍頓丘，于毒等人攻打東武陽。
諸將建議曹操回軍救援，曹操欲圖趁機襲擊敵軍本屯，對諸將說：“孫臏救趙而攻魏，耿弇欲攻西安而攻臨淄。讓敵軍知道我軍西進而回撤，則東武陽之急自解。如果他們不回，我就能攻破他們的本屯，他們卻必不能拿下東武陽。”
于是，曹操引兵西入山，攻打于毒等人的本屯。
于毒得知后，放棄攻打東武陽而回軍。
曹操邀擊眭固，又在內黃與匈奴於夫羅交戰，皆大獲全勝。
初平三年（192年），青州黃巾軍大獲發展，連破兗州郡縣，陣斬兗州刺史劉岱。
濟北國相鮑信與州吏萬潛等人來到東郡迎曹操領兗州牧。
曹操和鮑信合軍進攻黃巾，戰于壽張之東，鮑信戰死。
曹操“設奇伏，晝夜會戰”，終于將黃巾擊敗。
當年冬天，他獲得降卒三十余萬，人口百余萬。
曹操收其精銳，組成軍隊，號稱青州兵。
這樣，曹操又有了一支頗具戰斗力的軍隊。
同時，袁術與袁紹交戰，向公孫瓚求援。
公孫瓚讓劉備屯高唐，單經屯平原，陶謙也屯兵發干，以此進逼袁紹。
曹操幫助袁紹擊破陶謙諸軍。
初平四年（193年）春天，袁術因糧道被劉表切斷，引軍進入陳留，屯兵封丘，黑山軍及南匈奴於夫羅部都幫助袁術。
袁術令部將劉詳屯匡亭，曹操率兵攻打劉詳，袁術帶兵救援，雙方激戰，曹操大獲全勝。
袁術兵敗，退守封丘，曹操率軍包圍，圍勢未成，袁術又逃往襄邑。
曹操追到太壽，決開渠水灌城。
袁術逃往寧陵，曹操再次追擊，袁術只得逃往九江。
夏季，曹操回到定陶。
當時，陶謙與闕宣共同舉兵，攻取泰山的華、費二縣，接著率軍攻入兗州南部的任城。
秋季，曹操率軍征討陶謙，進兵徐州，向東南擴展勢力，攻克徐州十余城。
曹操與陶謙大戰于彭城，陶謙軍敗退，死亡的人數將近一萬，泗水為之不流。
陶謙退守郯縣，不敢出戰。
不久，曹操軍糧將盡，撤圍回軍。
興平元年（194年）春天，曹操回到兗州。
當初，曹操的父親曹嵩和弟弟曹德在前來曹操處途中，被陶謙派兵殺害，因此曹操志在東征。
夏季，曹操再征徐州，攻破五城，略地至東海，回軍在郯縣擊破劉備、曹豹，又攻破襄賁，所過之處多所殘戮。
東郡守備陳宮對曹操不滿，于是與陳留太守張邈、張邈之弟張超、從事中郎許汜及王楷等同謀叛亂，迎呂布為兗州牧。
當時，只有鄄城和東郡的范縣、東阿兩縣尚在曹操掌握之中，分別由司馬荀彧和壽張縣令程昱、東郡太守夏侯惇等堅守，形勢異常危急。
曹操從徐州趕回，聽說呂布屯于濮陽，遂進軍圍攻濮陽。
二軍相持百余日，蝗災大起，雙方停戰，曹操軍還鄄城。
此時，曹操失去了兗州，軍糧已盡。
袁紹派人來勸說，想讓曹操投靠他，讓曹操舉家遷到鄴縣當人質。
曹操本打算答應，但被程昱勸阻。
十月，曹操到達東阿。
興平二年（195年）春，曹操襲擊定陶，濟陰太守吳資保守南城，曹操攻之不下。
呂布率軍前來，曹操將他擊敗。
夏季，曹操攻擊巨野，呂布率軍救援巨野。
曹操擊破呂布軍，斬殺屯駐巨野的薛蘭等人，呂布會合陳宮率領一萬多人從東緡趕來。
此時，曹操士兵大多數都外出收麥了，留下的不足一千，營壘也不堅固。
曹操命婦人守于城上，士兵拒守呂布。
營壘西邊有一條大堤，南邊是幽深的樹林，呂布懷疑曹操有埋伏，對部下說：“曹操詭計多端，切勿進了他的埋伏。”
于是，率兵駐扎在曹操營壘南邊十多里的地方。
次日，呂布再次前來，曹操令一半士兵藏于堤壩之內，一半在外誘敵。
呂布進軍，曹操派輕兵挑戰。
雙方交戰后，曹操的伏兵出動，步騎并進。
呂布大敗，鼓車被曹操繳獲，曹操一直追到呂布軍營才返回。
呂布連夜逃走，曹操追擊，又攻克定陶，分兵平定諸縣。
呂布前往徐州投奔劉備，張邈與呂布同行，留張超駐守雍丘。
七月，因關中李傕、郭汜的火拼，漢獻帝從長安東歸。
八月，曹操圍攻張超于雍丘。
十月，獻帝正式拜曹操為兗州牧。
十二月，曹操攻破雍丘，張超自殺。
曹操夷滅張邈三族，而張邈在求救袁術的途中被部下所殺。
自此，兗州平定，曹操又率軍東攻陳國之地。
建安元年（196年）二月，曹操討平汝南、潁川一帶的黃巾軍何儀、劉辟等部，獻帝封曹操為建德將軍。
六月，經曹操謀士董昭的勸說，獻帝身邊的將軍楊奉等人表請拜曹操為鎮東將軍，襲父費亭侯之爵位。
早在初平三年（192年），曹操的謀士毛玠就提出了“奉天子以令不臣，修耕植，畜軍資”的戰略性建議，曹操深以為是。
此時，曹操想迎接獻帝，其謀臣大多認為山東尚未平定。
而獻帝身邊的韓暹、楊奉等又驕橫難制，所以不贊成迎接，只有荀彧、程昱極力勸迎。
最后，曹操決定派曹洪率兵迎接獻帝，但被衛將軍董承與袁術的部將萇奴據險阻止。
建安元年（196年）七月，獻帝回到洛陽，董承為牽制韓暹等跋扈的將領，又密召曹操來洛陽。
八月，曹操來到洛陽，奏明韓暹、張楊之罪。
韓暹逃奔楊奉，因護駕之功被獻帝特赦。
于是，曹操殺了侍中臺崇、尚書馮碩、議郎侯祈，封董承等十三人為列侯，曹操本人亦領司隸校尉、錄尚書事。
隨后，曹操聽從董昭建議，于九月遷獻帝于許縣，他本人被封為大將軍，進封武平侯。
楊奉對遷許之舉非常不滿，打算攔路截擊，結果失敗。
十月，曹操討平楊奉。
十一月，曹操升任司空，行車騎將軍事，總攬朝政。
這一年，曹操聽從棗祗、韓浩等人的建議，開始實行屯田制。
劉備遭到呂布襲擊，投奔曹操。
程昱勸道：“依我看劉備有雄才大略，又深得民心，不會久居人下，不如趁早除掉他。”
曹操回答：“如今正是招攬賢才之時，為殺一人而失天下人心，不可。”
建安二年（197年）正月，曹操討伐割據宛城的張繡，駐軍淯水。
張繡舉眾投降，旋即復叛，曹操長子曹昂、侄子曹安民、猛將典韋戰死。
曹操引兵退還舞陰，張繡派兵來攻，被曹操擊退。
張繡奔往穰城，與劉表聯合。
曹操對諸將說：“我收降張繡等人，卻犯了沒有立即扣押人質的錯誤，所以遭到了失敗。我明白了失敗的原因，請大家看著，從今以后我不會再失敗了。”
之后，回到許縣。
割據淮南的袁術僭號，呂布把他的使者送到許縣，袁術怒而進攻呂布，結果為呂布所破。
九月，袁術侵略陳國，曹操聞訊親自東征袁術。
袁術得知曹操親自來，便棄軍而逃，留橋蕤等四將鎮守。
曹操到后，斬殺橋蕤等將。
袁術渡淮而走，曹操也回到許縣。
十一月，曹操南征荊州，到達宛城。
劉表部將鄧濟據湖陽，曹操生擒鄧濟，湖陽也投降。
之后，曹操又攻下了舞陰。
建安三年（198年）正月，曹操回到許縣。
三月，曹操再次南征，圍攻張繡于穰城。
四月，曹操所遣的謁者裴茂率中郎將段煨討李傕，夷三族。
五月，劉表派兵救援張繡，并打算截斷曹操后路。
曹操引軍退還，張繡追擊，曹操軍無法前行。
于是，結成連營，得以慢慢前進。
曹操寫信給荀彧說：“賊軍緊追我軍，雖然我軍日行數里，但我算好了，到安眾縣時，一定能打敗張繡。”
到了安眾縣，張繡和劉表聯軍守在險要地方，曹操軍前后受敵。
于是，曹操派人趁天黑在險要處挖鑿一條地道，把輜重物資全部偷運過去，又設下伏兵。
天明時，張繡軍認為曹操已逃走，全軍追趕。
曹操便派出步兵、騎兵兩面夾攻，把賊軍打得大敗。
七月，曹操回到許都。
荀彧問曹操：“之前您料定一定會打敗敵軍，這是為什么？”
曹操回答：“敵人阻止我回歸的部隊，與我軍死地戰，我由此而知一定會勝利。”
九月，曹操東征徐州，進攻久與他為敵的呂布。
十月，曹操破彭城，擒獲呂布的彭城相侯諧。
曹操進軍下邳，呂布親自率騎兵逆擊，曹操大破呂布，擒獲他的部將成廉，并追擊到下邳城下。
呂布欲圖投降，陳宮等人勸阻呂布，又勸呂布出戰，呂布再次戰敗，退回城內固守。
曹操用荀攸、郭嘉之計，決泗、沂之水灌城。
十二月，呂布部將魏續、宋憲等生擒陳宮，歸降曹操。
呂布見大勢已去，下城投降。
曹操將呂布、陳宮、高順等人處死，收降呂布部將張遼以及泰山豪杰臧霸、孫觀等人，初步控制了徐州。
曹操將青、徐二州委托給臧霸等泰山諸將。
當初，曹操統領兗州時，任命東平人畢諶為別駕。
后來張邈叛亂，劫走畢諶的母親、弟弟、妻小，曹操放任畢諶離去，對他說：“你的老母親在張邈那里，你可以離開。”
畢諶叩頭表示不會懷有二心，曹操十分贊賞他，并感動地流下了眼淚。
但是畢諶出去后，還是選擇逃到張邈那里。
呂布敗亡后，曹操生擒畢諶，眾人為他擔心。
曹操說：“作為人能孝順他的親人，不也會忠于他的君主嗎！這正是我所需要的人。”
于是，任命他為魯國相。
建安四年（199年）二月，曹操到達昌邑。
張楊的部將楊丑殺死張楊響應曹操，眭固又殺楊丑，率眾屯射犬，聯合袁紹。
曹操把司空之位讓給太仆趙岐，朝廷不從。
朝廷因曹操討呂布有功，為他增邑三千戶，曹操固辭不受。
四月，曹操親征河內，并派史渙、曹仁擊殺眭固。
曹操渡河進圍射犬，河內太守繆尚與張楊手下長史薛洪率眾投降。
曹操取得河內郡，把勢力范圍擴張到黃河以北。
當初，曹操舉魏種為孝廉。
兗州叛亂時，曹操說：“唯獨魏種不會背叛我。”
結果，魏種叛逃。
曹操怒道：“你魏種只要沒有南逃越地、北走胡地，我就一定不會放過你！”
取得射犬后，魏種被生擒。
曹操既往不咎，下令給魏種松綁，并任命他為河內太守，將河北之事委托給他。