雖然這個理由有點牽強，但是，畢竟薛仁貴有先皇御賜的打王鞭和代天討逆的旗號。遂命令以羅成爲左路先鋒，麾下尉遲恭，周倉等人，領三萬大軍，從北海國出兵。並且還以張飛爲右路先鋒，麾下高順，管亥等人。同樣率領三萬大軍，從汝南郡出兵。
薛仁貴則親領四萬大軍緊隨其後，隨軍大將周青，周文，周武兄弟，姜興本，姜興霸兄弟，還有程咬金，新投靠的單雄信則被薛仁貴派遣到北方大營了。隨軍軍師戲志才。
徐茂公先言，說道：“雖然主公並不喜劉備，但是仍然可以給劉備書信一封。想呂布偷樑換柱取了徐州，劉備必定是耿耿於懷的，若由此機會，劉備怎能不與呂布反目。”
薛仁貴再說道：“茂公此計雖然不錯，但是，吾還有更穩妥一計，不過，且先按你的計劃，給劉備送信去吧。”
徐茂公從命，便派人給劉備送去書信一封。
而薛仁貴卻是在衆將散後和徐茂公說道：“軍師，此地由你坐鎮，我需往徐州去一趟，如此，如此，這般，這般。”
徐茂公頓時一頭冷汗，說道：“主公此計甚妙，只是如此小事，怎勞主公親自前往？”
薛仁貴卻是語出驚人的說道：“千軍易得，一將難求。關羽，許褚皆是萬人敵，只可惜此兩人只對劉備忠心耿耿。”
徐茂公說道：“難道主公是想。。。。。。只是，千金之子坐不垂堂、主公此舉是不是太過危險，不如讓其他人去？”
薛仁貴說道：“不可，關羽，許褚都是萬人敵，其他人我放心不下。必須我自己親自去，軍師不必再勸了。”
徐茂公只好說道：“那，主公保重。”
薛仁貴說道：“軍師只需安心坐鎮大營，我已經下令讓姜興霸和周文兩人回來了，今天下午應該就能過來了，此行我讓周青與我同往。”
徐茂公只能應了一聲，便目送着周青和薛仁貴遠去了。
且說呂布在徐州，每當賓客宴會的時候，陳珪父子必定盛讚呂布施恩步德。
姚廣孝不滿，私下裡告訴呂布說道：“陳珪父子當面奉承將軍，但是其心不可測，將軍應該小心提防的。
呂布發怒斥責姚廣孝說道：“你無端獻讒言，想陷害好人嗎？“
姚廣孝出來嘆息說道：“不納忠言，我們怕是一定要遭殃了！”
想要放棄呂布去投奔別處，卻又不忍心；又怕被人嘲笑。於是整天悶悶不樂。
有一天，帶着幾個騎兵離小沛地面圍打獵解除煩悶，忽然聽見一聲弓弦聲響，其聲如若奔雷，心想定然是一位勇士開了重弓纔會有如此動靜，不由得循聲找了過去，沒找到什麼射箭的勇士，卻是看見一個騎兵，在驛馬官道上，飛奔向前走。
姚廣孝十分的懷疑，放棄了圍場，引隨從的騎兵從小路追趕上，問道：“你是什麼地方使者？”
那姚廣孝知道是呂布手下人，所以也不做回答。
姚廣孝下令搜查他的身上，找到了一封劉備秘密寫給薛仁貴的信。
姚廣孝就連人與書，拿見呂布。
呂布問姚廣孝這是怎麼回事。
那個被抓到的使者說道：“驃騎大將軍差人給我家主公送信，今日我帶着回信去兗州的，不過在下並不知道書中所說的是什麼事。”於是呂布拆書信細細看來。
書中說道：“備封驃騎大將軍之命，欲要攻打呂布，豈敢不夙夜用心。但是被兵微將寡，不敢輕易妄動。驃騎大將軍興正義之師，備願爲前鋒。”
來上次他惜敗給薛仁貴，就一直讓他耿耿於懷。現在，薛仁貴居然先手來攻打他，還和劉備勾結，呂布怎能不怒？
呂布見了，大罵說道：“二賊怎麼敢如此！”於是將使者斬首。
先讓姚廣孝、臧霸、聯結泰山寇孫觀、吳敦、尹禮、昌，向東迎戰薛仁貴的右路先鋒。
令張遼取沛城，攻打劉備。令宋憲、魏續向西迎戰薛仁貴的左路先鋒。
呂布親自總領中軍爲三路救援響應。
且說張遼等人率兵出徐州，即將到達小沛，有人報告給了劉備。
劉備急與衆人商議。
孫乾說道：“可快告急於驃騎大將軍。“
劉備說道：“誰可以去許都告急？”
臺階下一人出來說道：“在下願往。”
這個人乃是劉備同鄉人，姓簡，名叫雍，字憲和，現在是劉備的幕僚。
劉備就寫了信給簡雍，使連夜前往兗州求援；一面整頓守城器械。
劉備守着南門，孫乾守門，關羽守西門，許褚守東門。
張遼軍到，劉備在城樓上問道：“我和奉先沒有矛盾，爲什麼率領軍隊到這裡？“
先是張遼手下副將率先趕到，他便迎着劉備的話說道：“你勾結薛仁貴，想害我主，現在事情已經敗露，爲什麼不自縛去見我家主公！”
說完，便引軍攻城。劉備緊閉城門不出。
第二天，張遼率領軍隊攻打西門。
關羽在城上對他說道：“公儀表不俗，爲什麼失身於賊？”張遼低頭不語。雲長知道這個人有忠義之氣，更不用惡言相加，也不出戰
。張遼帶兵撤退到東門，許褚便出來迎接挑戰。早有人報告給了關羽。關羽趕緊來東門看時，只見許褚纔出城，張遼軍已經撤退。
許褚想追趕，關羽急忙把他召入城內。
許褚說道：“彼懼而退，何不追之。”
關羽說道：“此人武藝不在你我之下。因我以正言感之，頗有自悔之心，故不與我等而戰。”
許褚這才明白，只讓士卒堅守城門，更不出戰。
呂布卻是在自己的探馬打聽之下，知道薛仁貴已起十萬大軍南下，若是不克，恐怕還會有援軍而來。所以呂布在姚廣孝的建議之下，決定先攻打劉備，以求安內。
隨即呂布親率三萬大軍趕往小沛，和張遼匯合。
劉備在小沛得到了消息，便聽從了軍師酈食其的辦法，遂派許褚和關羽都在城外安營紮寨，再加上小沛城，兩寨一城成掎角之勢，互相照應。
卻說張遼出擊關羽軍寨，呂布親自率兵攻打許褚軍寨。關羽、張飛都出來迎接挑戰，劉備率兵兩路接應。
呂布命姚廣孝分軍從背後殺來，關羽、許褚兩支軍隊都被呂布殺得潰散，劉備率領幾十個騎兵逃回沛城。呂布趕來，玄德急忙叫城上士兵放下吊橋。呂布緊隨其後。
城上想要放箭阻擊呂布軍，又怕射傷了劉備。被呂布乘勢殺入城門，把守門將士抵不住，都四散奔逃躲避。
呂布招軍入城。玄德見形勢危急，回到家不到，只得拋棄了妻子小，穿城而過，走出西門，匹馬逃難，卻沒看見，遠處樹林裡面有兩騎穿着呂布軍裝的騎兵，其中一個人挽弓出箭，只聽“彭”的一聲，劉備應聲落馬，而劉備的馬兒像是受到了驚嚇，等劉備落馬之後，嘶叫着跑開了。
小沛城下的呂布軍聽見這邊有動靜，急忙的過去查看，一看竟然是劉備，身中一箭，顯然是已經命喪黃泉了。趕忙割了劉備的首級去找呂布，姚廣孝領賞。
呂布趕到劉備家中，糜竺出來迎接，隨即說道：“我聽說大丈夫不害別**子。現在與您爭奪天下的人，只不過是薛仁貴罷了。希望將軍可以可憐。”
呂布說道：“我和玄德是老朋友，怎麼會忍心殺害他的妻子。”就讓劉備妻兒由糜竺率領，前往徐州安置。
呂布親自率軍到山東兗州境上，留張遼駐守小沛。許褚、關羽兩人也各自得到些人馬，在山中駐紮，並且派遣出兵馬去找尋劉備。
當聽斥候打聽到劉備被呂布軍射殺了，還被割了首級去領賞。關羽和許褚兩個人都是虎目怒睜，許褚當即就要點起騎兵去攻打呂布，要爲劉備報仇。
關羽還比較冷靜，看見許褚這個樣子就要出去，慌忙拉住他，問道：“三弟，意欲何爲？”
許褚怒氣衝衝的答道：“當然是去殺了呂布這個直娘賊，好爲大哥報仇！難不成我還能去投奔那三姓家奴？！”
關羽知道許褚在氣頭上，也並不和他計較，說道：“你現在去找呂布，我怕你連他的面都見不到，就已經全軍覆沒了！”
許褚顯然也是知道這個道理，眼中多了一絲希望，但還是倔強的說道：“那難道大哥的仇就不報了？”
關羽說道：“大哥的仇，自然是要報的，吾定當親手砍下呂布小兒的頭顱！只是現在咱們這些兵力，並不可能對抗呂布的大軍，你我兄弟二人可以等薛將軍的大軍與呂布交手之時，你我二人兵分兩路，你藉助大哥以前在徐州的號召力，趁呂布出兵之時，想辦法看看能不能重新佔回徐州城，我則趁呂布大軍與薛將軍大軍交戰之時，從中殺出，去取呂布項上人頭！”
許褚卻是嗔怒道：“二哥，這件事情九死一生，而且之前徐州的事情我也從來不管，徐州的人馬不一定對我有感情，還是我去殺那賊呂布。”