吕布领七万人马，一路东进，直奔兖州而来。
接近陈留之时，有军士前来报告。
军士禀报称：“将军，前方一位自称陈宫的文士前来求见。”
吕布听得陈宫二字，顿时喜出望外，因为他知道，自己命中注定的首席军师终于到来了。
吕布忙点头道：“传他进来。”
吕布见到陈宫，先下马跪拜道：“在下吕布，久仰公台先生大名，只恨军务繁忙，未有机会与先生谋面。今日终于得以一见，实乃三生有幸之事也。公台先生在上，请受在下一拜。”
陈宫忙弯腰将吕布扶起，并谦虚道：“在下不过张邈麾下一介小小从事，何敢烦劳将军如此大礼。”
吕布请求道：“如今汉室衰微，天下大乱。曹操假借为父报仇之名，侵犯徐州，杀戮无辜民众。本将如今奉朝廷圣旨，讨伐兖州，拯救徐州黎民百姓。还望先生能够看在百姓份上，辅佐本将，助本将一臂之力。”
陈宫当即答应下来，说道：“在下虽官职低微，才疏学浅，不过略有计谋，却蒙将军如此抬举，实乃三生有幸。当年在下任中牟县令之时，曹操刺杀董卓未遂，逃亡至中牟县时，为在下所擒，在下以为他心系国家，便决定弃官随之一路逃亡。却未曾想，这厮虽说杀不了董卓，但杀起平民百姓来，那可是毫不手软，他先是杀害恩人吕伯奢一家，之后以为父报仇为名攻打徐州，所到之处一片狼藉，鸡犬不留。常言道：‘知人知面不知心’，此话绝非虚言。在下若继续保他，又何异于助纣为虐？倘若在下跟了他这等心狠手辣之人，后果定当不堪设想，应当弃暗投明才是。所以在下当即选择弃他而去，另寻明主。在下仰慕将军大名久矣，今日见之，果然是英武过人，一表人才也。将军不远千里而来，吊民伐罪，围魏救赵，拯救徐州，居功甚伟，实乃当世之英雄也。如若将军不弃，在下愿与将军出谋划策，助将军大展神威，攻取兖州，讨灭曹操，扫平中原，一统天下。”
吕布知道，在原本的历史当中，兖州之战早期之时，吕布因采纳陈宫之言，所以屡次战胜曹操，后期则因先前胜仗而骄傲自大，迷信个人武力，不听陈宫计谋，结果作战失利，为曹操逐出兖州，被迫往东投奔徐州的刘备。
到了徐州以后，陈宫因吕布不听自己计谋，心下甚为不满，故而一度同袁术相互勾结，与郝萌一道发动兵变未遂。事后吕布为人宽宏大量，未曾追究陈宫罪行，方才使得陈宫变得死心塌地，忠心耿耿。
吕布本欲与袁术结盟，将女儿嫁往淮南，因陈珪、陈登父子二人从中破坏，导致吕布杀害袁术使者，吕、袁联盟宣告破裂。袁术为之大怒，命大将张勋与白波军将领杨奉、韩暹等人领兵数万，来犯徐州。吕布采纳陈珪、陈登父子计谋，策反杨、韩二人，大破袁术，斩将十员，虎涉江淮，收获极多。
此次战争当中，虽说未曾看到陈宫出谋划策，但并不足以证明他在智谋方面不及陈氏父子，而是出于立场问题，他不主张吕布与袁术为敌，而是主张吕、袁两家应当联起手来，共同对抗曹操。
经过这场战斗，袁术元气大伤，回天无力。吕布虽说短时间内收获较大，但以长远眼光来看，亦是小赢大输。吕布重创了身边唯一可以作为盟友的一方势力，为他不久将来的败亡埋下了伏笔。下邳之战时，袁术即使想来救援吕布，亦是心有余而力不足矣。
江淮之战过后，吕布对陈登父子信赖有加，对陈宫则是愈加疏远，悲剧悄然萌生。结果建安三年，曹操、刘备二路人马联手来犯徐州，陈登亦临阵倒戈，与曹、吕两军相配合，三面夹攻，使吕布所处局面更加不利。
陈宫与吕布提议，由自己负责在下邳城中驻守，吕布则领军屯于城外，如曹军来攻，彼此之间可以相互救应，同时建议吕布能够率领骑兵部队，切断曹军粮道。此计虽说并非万全之策，但从当时情况看来，未必不是一项可行之举。如果这般，吕布即使不能够击败曹操，亦有机会突围而走，从而避免了白门楼上的悲剧结局。可惜吕布为人疑心太重，又听信妻子所言，未能采纳陈宫计谋，结果使得曹操水淹下邳，侯成、宋宪、魏续等将开城出降，吕布与陈宫、高顺等人，尽数为曹操擒获斩首。
如今自己穿越成为吕布以来，陈宫主动投奔自己，自己无论如何，都必须对其加以重用，尽量发挥他的最大使用价值，否则难免会辜负了对方对自己的一片忠心。
不过于此同时，吕布又十分清楚，陈宫此人虽说颇有智谋，但反应较为迟缓，缺少随机应变能力，与当世某些顶级谋士相比，尚且存在有不小差距，自己欲成大业，仅依靠这样一位谋士还远远不够。
吕布命自己麾下主簿法正、杨修二人与陈宫相见，吩咐他们拜陈宫为师，跟随陈宫学习策略兵法。因为他心下十分清楚，如今法、杨二人尚且年少，经验明显不足，暂且不足以独当一面，因此必须先在前辈身边学习一段时间，方可参与实战。
陈宫与吕布提议道：“在下愿凭三寸不烂之舌，往陈留说服张邈，劝其迎将军入主兖州。”
吕布许之，命陈宫往陈留而去。
陈宫只身来到陈留，与张邈会面，大展其游说之能。
陈宫游说道：“今雄杰并起，天下分崩。君以千里之众，当四战之地，抚剑顾盼，亦足以为人杰，而反受制于人，不亦鄙乎！今曹军征东，其处空虚，而吕布乃当世英雄，无比之士，若权迎之，共取兖州，观天下之形势，随时变通，霸业可图矣。”
张邈从其所言，当即表示向吕布效忠，并欢迎吕布到来。
吕布大喜，与严慧、貂蝉、蔡琰、金元武、高顺、张辽、曹性、成廉、徐晃、法正、马钧、华雄、马超、马岱、庞德、阎行、徐荣等将领率军前行，进入陈留境内。
与此同时，泰山军首领臧霸亦领军前来相助吕布。臧霸字宣高，泰山华阴人也，为人性如烈火，胆气过人，生得身长八尺，体若奔狼，惯使两条镔铁锏，有万夫不当之勇。
吕布来到陈留，忽然想起了什么。
在原本的历史上，吕布与曹操争夺兖州之时，曾一度使曹操陷入包围，几乎丧命。就在此关键时刻，曹军中忽然杀出一员勇将，名唤典韦，手使双铁戟，奋力杀开包围，掩护曹操而去。据说典韦此人，原为张邈麾下将领，因同帐下人不和，方才转投曹操。单论武艺，此人绝不亚于自己早年水准，更兼忠心耿耿，是个值得招揽的人物。
吕布想到此处，遂问张邈道：“不知张将军麾下，可有一位名叫典韦的壮士么？”
张邈点头道：“吕将军所言极是。典壮士乃陈留己吾人也，其人形貌魁梧，力大无穷，为人侠肝义胆，好与人打抱不平。早年，其同乡好友刘氏与睢阳人李永有仇，典韦便主动为刘氏复仇。李永曾任富春长，家中备卫甚为严谨，典韦乃驾车携带鸡酒，装作闲人在门外等候，待李永亲自出府时，典韦拔出匕首，将李永夫妻一并刺杀，取出车上刀戟，步行离去，整个集市俱为之惊骇，虽有数百官军随后追赶，却无一人敢于接近。典韦步行四五里，遭遇李永手下多人拦截，与之战斗不久，即脱身而去。至此之后，典韦便为兖州众多豪杰之士所赏识。末将起兵之时，典韦于末将帐下担任军士，军中牙门旗十分长大，无人能举，而典韦仅一只手即将之擎起，足见其神力非凡。其所使之军器，乃两枝铁戟，重八十斤，臂上挟之。飞马刺人，如同无物。只是他最近貌似与战友不和，意欲投奔曹操，末将既无办法将其挽留，又无法狠下心来，将其直接杀害，还请将军早些定夺。”
吕布笑道：“好，麻烦你现在就去叫典韦过来，本将自有办法将其说服。”
不多时，典韦带到，其人生得身长一丈，腰大数围，虎背熊腰，淡黄面皮，马上挺双铁戟，重八十斤，背上数十支短戟，取敌将首级，如同探囊取物一般，有万夫不当之勇，乃是张邈帐下第一员勇将。
典韦见到吕布，乃行礼道：“末将典韦，参见吕将军。”
吕布明知故问，试探道：“听闻典将军与战友不和，意欲别投他处，不知可有此事？”
