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