初平二年（191年），黑山贼于毒、白绕、眭固等率十多万人攻打魏郡、东郡，东郡太守王肱不能抵御。
曹操引军入东郡，在濮阳击破白绕。
因此，袁绍表曹操为东郡太守，治所在东武阳。
初平三年（192年），曹操驻军顿丘，于毒等人攻打东武阳。
诸将建议曹操回军救援，曹操欲图趁机袭击敌军本屯，对诸将说：“孙膑救赵而攻魏，耿弇欲攻西安而攻临淄。让敌军知道我军西进而回撤，则东武阳之急自解。如果他们不回，我就能攻破他们的本屯，他们却必不能拿下东武阳。”
于是，曹操引兵西入山，攻打于毒等人的本屯。
于毒得知后，放弃攻打东武阳而回军。
曹操邀击眭固，又在内黄与匈奴於夫罗交战，皆大获全胜。
初平三年（192年），青州黄巾军大获发展，连破兖州郡县，阵斩兖州刺史刘岱。
济北国相鲍信与州吏万潜等人来到东郡迎曹操领兖州牧。
曹操和鲍信合军进攻黄巾，战于寿张之东，鲍信战死。
曹操“设奇伏，昼夜会战”，终于将黄巾击败。
当年冬天，他获得降卒三十余万，人口百余万。
曹操收其精锐，组成军队，号称青州兵。
这样，曹操又有了一支颇具战斗力的军队。
同时，袁术与袁绍交战，向公孙瓒求援。
公孙瓒让刘备屯高唐，单经屯平原，陶谦也屯兵发干，以此进逼袁绍。
曹操帮助袁绍击破陶谦诸军。
初平四年（193年）春天，袁术因粮道被刘表切断，引军进入陈留，屯兵封丘，黑山军及南匈奴於夫罗部都帮助袁术。
袁术令部将刘详屯匡亭，曹操率兵攻打刘详，袁术带兵救援，双方激战，曹操大获全胜。
袁术兵败，退守封丘，曹操率军包围，围势未成，袁术又逃往襄邑。
曹操追到太寿，决开渠水灌城。
袁术逃往宁陵，曹操再次追击，袁术只得逃往九江。
夏季，曹操回到定陶。
当时，陶谦与阙宣共同举兵，攻取泰山的华、费二县，接着率军攻入兖州南部的任城。
秋季，曹操率军征讨陶谦，进兵徐州，向东南扩展势力，攻克徐州十余城。
曹操与陶谦大战于彭城，陶谦军败退，死亡的人数将近一万，泗水为之不流。
陶谦退守郯县，不敢出战。
不久，曹操军粮将尽，撤围回军。
兴平元年（194年）春天，曹操回到兖州。
当初，曹操的父亲曹嵩和弟弟曹德在前来曹操处途中，被陶谦派兵杀害，因此曹操志在东征。
夏季，曹操再征徐州，攻破五城，略地至东海，回军在郯县击破刘备、曹豹，又攻破襄贲，所过之处多所残戮。
东郡守备陈宫对曹操不满，于是与陈留太守张邈、张邈之弟张超、从事中郎许汜及王楷等同谋叛乱，迎吕布为兖州牧。
当时，只有鄄城和东郡的范县、东阿两县尚在曹操掌握之中，分别由司马荀彧和寿张县令程昱、东郡太守夏侯惇等坚守，形势异常危急。
曹操从徐州赶回，听说吕布屯于濮阳，遂进军围攻濮阳。
二军相持百余日，蝗灾大起，双方停战，曹操军还鄄城。
此时，曹操失去了兖州，军粮已尽。
袁绍派人来劝说，想让曹操投靠他，让曹操举家迁到邺县当人质。
曹操本打算答应，但被程昱劝阻。
十月，曹操到达东阿。
兴平二年（195年）春，曹操袭击定陶，济阴太守吴资保守南城，曹操攻之不下。
吕布率军前来，曹操将他击败。
夏季，曹操攻击巨野，吕布率军救援巨野。
曹操击破吕布军，斩杀屯驻巨野的薛兰等人，吕布会合陈宫率领一万多人从东缗赶来。
此时，曹操士兵大多数都外出收麦了，留下的不足一千，营垒也不坚固。
曹操命妇人守于城上，士兵拒守吕布。
营垒西边有一条大堤，南边是幽深的树林，吕布怀疑曹操有埋伏，对部下说：“曹操诡计多端，切勿进了他的埋伏。”
于是，率兵驻扎在曹操营垒南边十多里的地方。
次日，吕布再次前来，曹操令一半士兵藏于堤坝之内，一半在外诱敌。
吕布进军，曹操派轻兵挑战。
双方交战后，曹操的伏兵出动，步骑并进。
吕布大败，鼓车被曹操缴获，曹操一直追到吕布军营才返回。
吕布连夜逃走，曹操追击，又攻克定陶，分兵平定诸县。
吕布前往徐州投奔刘备，张邈与吕布同行，留张超驻守雍丘。
七月，因关中李傕、郭汜的火拼，汉献帝从长安东归。
八月，曹操围攻张超于雍丘。
十月，献帝正式拜曹操为兖州牧。
十二月，曹操攻破雍丘，张超自杀。
曹操夷灭张邈三族，而张邈在求救袁术的途中被部下所杀。
自此，兖州平定，曹操又率军东攻陈国之地。
建安元年（196年）二月，曹操讨平汝南、颍川一带的黄巾军何仪、刘辟等部，献帝封曹操为建德将军。
六月，经曹操谋士董昭的劝说，献帝身边的将军杨奉等人表请拜曹操为镇东将军，袭父费亭侯之爵位。
早在初平三年（192年），曹操的谋士毛玠就提出了“奉天子以令不臣，修耕植，畜军资”的战略性建议，曹操深以为是。
此时，曹操想迎接献帝，其谋臣大多认为山东尚未平定。
而献帝身边的韩暹、杨奉等又骄横难制，所以不赞成迎接，只有荀彧、程昱极力劝迎。
最后，曹操决定派曹洪率兵迎接献帝，但被卫将军董承与袁术的部将苌奴据险阻止。
建安元年（196年）七月，献帝回到洛阳，董承为牵制韩暹等跋扈的将领，又密召曹操来洛阳。
八月，曹操来到洛阳，奏明韩暹、张杨之罪。
韩暹逃奔杨奉，因护驾之功被献帝特赦。
于是，曹操杀了侍中台崇、尚书冯硕、议郎侯祈，封董承等十三人为列侯，曹操本人亦领司隶校尉、录尚书事。
随后，曹操听从董昭建议，于九月迁献帝于许县，他本人被封为大将军，进封武平侯。
杨奉对迁许之举非常不满，打算拦路截击，结果失败。
十月，曹操讨平杨奉。
十一月，曹操升任司空，行车骑将军事，总揽朝政。
这一年，曹操听从枣祗、韩浩等人的建议，开始实行屯田制。
刘备遭到吕布袭击，投奔曹操。
程昱劝道：“依我看刘备有雄才大略，又深得民心，不会久居人下，不如趁早除掉他。”
曹操回答：“如今正是招揽贤才之时，为杀一人而失天下人心，不可。”
建安二年（197年）正月，曹操讨伐割据宛城的张绣，驻军淯水。
张绣举众投降，旋即复叛，曹操长子曹昂、侄子曹安民、猛将典韦战死。
曹操引兵退还舞阴，张绣派兵来攻，被曹操击退。
张绣奔往穰城，与刘表联合。
曹操对诸将说：“我收降张绣等人，却犯了没有立即扣押人质的错误，所以遭到了失败。我明白了失败的原因，请大家看着，从今以后我不会再失败了。”
之后，回到许县。
割据淮南的袁术僭号，吕布把他的使者送到许县，袁术怒而进攻吕布，结果为吕布所破。
九月，袁术侵略陈国，曹操闻讯亲自东征袁术。
袁术得知曹操亲自来，便弃军而逃，留桥蕤等四将镇守。
曹操到后，斩杀桥蕤等将。
袁术渡淮而走，曹操也回到许县。
十一月，曹操南征荆州，到达宛城。
刘表部将邓济据湖阳，曹操生擒邓济，湖阳也投降。
之后，曹操又攻下了舞阴。
建安三年（198年）正月，曹操回到许县。
三月，曹操再次南征，围攻张绣于穰城。
四月，曹操所遣的谒者裴茂率中郎将段煨讨李傕，夷三族。
五月，刘表派兵救援张绣，并打算截断曹操后路。
曹操引军退还，张绣追击，曹操军无法前行。
于是，结成连营，得以慢慢前进。
曹操写信给荀彧说：“贼军紧追我军，虽然我军日行数里，但我算好了，到安众县时，一定能打败张绣。”
到了安众县，张绣和刘表联军守在险要地方，曹操军前后受敌。
于是，曹操派人趁天黑在险要处挖凿一条地道，把辎重物资全部偷运过去，又设下伏兵。
天明时，张绣军认为曹操已逃走，全军追赶。
曹操便派出步兵、骑兵两面夹攻，把贼军打得大败。
七月，曹操回到许都。
荀彧问曹操：“之前您料定一定会打败敌军，这是为什么？”
曹操回答：“敌人阻止我回归的部队，与我军死地战，我由此而知一定会胜利。”
九月，曹操东征徐州，进攻久与他为敌的吕布。
十月，曹操破彭城，擒获吕布的彭城相侯谐。
曹操进军下邳，吕布亲自率骑兵逆击，曹操大破吕布，擒获他的部将成廉，并追击到下邳城下。
吕布欲图投降，陈宫等人劝阻吕布，又劝吕布出战，吕布再次战败，退回城内固守。
曹操用荀攸、郭嘉之计，决泗、沂之水灌城。
十二月，吕布部将魏续、宋宪等生擒陈宫，归降曹操。
吕布见大势已去，下城投降。
曹操将吕布、陈宫、高顺等人处死，收降吕布部将张辽以及泰山豪杰臧霸、孙观等人，初步控制了徐州。
曹操将青、徐二州委托给臧霸等泰山诸将。
当初，曹操统领兖州时，任命东平人毕谌为别驾。
后来张邈叛乱，劫走毕谌的母亲、弟弟、妻小，曹操放任毕谌离去，对他说：“你的老母亲在张邈那里，你可以离开。”
毕谌叩头表示不会怀有二心，曹操十分赞赏他，并感动地流下了眼泪。
但是毕谌出去后，还是选择逃到张邈那里。
吕布败亡后，曹操生擒毕谌，众人为他担心。
曹操说：“作为人能孝顺他的亲人，不也会忠于他的君主吗！这正是我所需要的人。”
于是，任命他为鲁国相。
建安四年（199年）二月，曹操到达昌邑。
张杨的部将杨丑杀死张杨响应曹操，眭固又杀杨丑，率众屯射犬，联合袁绍。
曹操把司空之位让给太仆赵岐，朝廷不从。
朝廷因曹操讨吕布有功，为他增邑三千户，曹操固辞不受。
四月，曹操亲征河内，并派史涣、曹仁击杀眭固。
曹操渡河进围射犬，河内太守缪尚与张杨手下长史薛洪率众投降。
曹操取得河内郡，把势力范围扩张到黄河以北。
当初，曹操举魏种为孝廉。
兖州叛乱时，曹操说：“唯独魏种不会背叛我。”
结果，魏种叛逃。
曹操怒道：“你魏种只要没有南逃越地、北走胡地，我就一定不会放过你！”
取得射犬后，魏种被生擒。
曹操既往不咎，下令给魏种松绑，并任命他为河内太守，将河北之事委托给他。