兴平二年（195年）夏天，吕布被彻底赶出了兖州。从他上一年夏天被张邈、陈宫迎进兖州到现在，刚好是一年时间。
一年之间，兖州八郡经历了天翻地覆的转变，也饱受了战火的摧残。所以，当战事告一段落之后，荀、毛等人就建议曹操暂停军事行动，发展地方经济，休养生息，恢复元气。
就在曹操考虑如何经营兖州的时候，失去地盘的吕布开始考虑自己的出路。他想了想，只好投奔徐州的刘备。
吕布此举实属无奈。他此时已是天下闻名的人物，论资历和知名度，刘备差得都不是一两个档次。但若论实力和地盘，吕布又跟刘备没法比。一个是新上任的徐州刺史，正跃跃欲试；一个被曹操打得落花流水，无处可去。
吕布亲自前往徐州来见刘备，表达愿意投靠的意愿。此时的刘备，已将大本营由徐州刺史部的治所郯县移到下沛国的治所下邳县。吕布见到刘备时，态度毕恭毕敬，跟刘备还套起了近乎：“我跟您都是边地人，真是缘分呀。我杀董卓，本应该得到天下人的敬重，但却没有人愿意接纳我，所以来投奔您。”
吕布是并州刺史部五原郡人，刘备是幽州刺史部涿郡人，本来拉不上老乡关系，但在吕布嘴里五原郡和涿郡都是边地，怎么说也算半个老乡吧。
吕布把刘备请到自己营帐中做客，喝完酒，邀请刘备到内帐之中，请刘备坐在自己妻子的床上，然后把自己的妻子叫出来拜见刘备，为刘备斟酒布菜（请备于帐中坐妇床上，令妇向拜，酌酒饮食）。吕布的妻子名字叫什么没有记载，但肯定不叫貂婵，因为那只是个虚构的人物。“貂婵”这两个字也不是人名，而是后宫里女官的名称。关于这方面的考据文章甚多，此处不予赘述了。
吕布跟刘备还称兄道弟，刘备生于桓帝延熹四年（161年），小曹操五岁，此时虚岁三十五岁。吕布生年不详，但他把刘备称为老弟，可见他比刘备年长。
印象中，此时的刘备应该是三缕长须飘在腮下，一副长者模样，而吕布则是英俊小生的打扮，成为女士们的偶像。看来，这纯属误解。
当年，担任青州刺史部平原国相的刘备接到了被黄巾军管亥部打得抬不起头来的北海国相孔融的求救，激动得瞬间心跳到了一百八：海内大名士孔融居然知道他刘备的名字！
而现在，刘备的心跳估计应该达到了二百：比孔融更有名、更有本事的当代名将吕布不仅知道他刘备的名字，而且对自己如此恭敬，愿意投奔到自己手下！
刘备好激动，也有点感动，他亲自迎接吕将军，给予盛情接待，对于吕布投奔自己的请求，更是想都没想就表示同意。
刘备犯了一个大错，在这一点上他不如袁术、袁绍甚至张杨。
先不说吕布的诚信记录有问题，仅从目前局势判断来看，刘备也不应该收留吕布。刚刚就任徐州刺史的刘备，立即受到袁术的攻击，无奈之下，刘备主动向袁绍表示效忠，并得到袁绍的认可，名义上他跟曹操一样，都属于袁绍阵营。
吕布是什么人？吕布是袁绍正在通缉的人，也是刚跟曹操拼得你死我活的人。刘备收留了吕布，将自己的战略思想引向了混乱。
刘备在微山湖南部一带被袁术压制得喘不上气的时候投靠了袁绍，虽然没有此后袁绍提供给刘备哪些具体帮助的记载，但刘备因为有袁绍作外援，已经度过了当时的危机。
日后，当刘备再次面临敌人攻击的时候，袁绍还会不会提供帮助呢？
这个问题刘备没有多想，可能他被吕布拍得有点晕乎，也可能他贪慕吕布手下的人马，出于现实利益的考虑，他正式接纳了吕布，并且给他找了一个好地方，安排了一个好差事。
刘备当年作为外援被陶谦引进的时候，陶谦让他驻扎在沛国的小沛，这里好比是日后荆州外围的新野，地处敌我之间的要冲，实际上是徐州的一面挡箭牌。
刘备给陶谦挡过一回箭，现在刘备又把这个光荣的任务转交到吕布手上，希望他给自己也挡一回箭。当然，这仅仅是刘备的个人想法。
小沛即沛县，汉高祖刘邦的老家，因为它属于沛国，为了在名字上有所区别，习惯上把它称为小沛。沛国不属于徐州刺史部，而属于豫州刺史部，如前所述，从地理位置上看，这里像是插在兖州跟徐州之间的一把剑。由于吕布到了豫州的地盘上，刘备顺便也送给吕布一个新头衔：豫州刺史。这个职务此前由刘备兼任，是陶谦生前表奏给刘备的，刘备此时已经担任了徐州刺史，就把豫州刺史让给了吕布。
豫州至少还有一个刺史叫郭贡，是袁术表奏的，郭贡之前，袁术还曾短暂地表奏过孙坚的侄子孙贲为豫州刺史，但不久就派他到南方工作去了。刘备让吕布当豫州刺史，目的至少有两个：一是替自己抵挡名义上的盟友、潜在的敌人曹操，二是跟自己眼前的敌人袁术抢地盘。
刘备盘算得很好，但事情的进展却不如他所想，因为他对吕布这个人实在太缺乏了解了。
第二年，也就是建安元年（196年）春天，袁术再次由寿春对刘备发起了进攻。刘备让张飞留守在下邳，自己率领关羽、赵云等人南下迎敌，双方交战的地点跟上次差不多，在盱眙、淮阴一带，即今天的微山湖南部地区。
在河网密布、丘陵纵横的江淮地带刘备跟袁术都没能取得速胜，双方陷入僵持，这样一来，刘备的后方基地出了问题。
刘备入主徐州以后，内部形势并不稳定，徐州本土派人士不是所有人都服气刘备，也有暗生不满的，下邳国相曹豹就是其中的一位。
曹豹见刘备被袁术牵制在南线作战，留守的张飞兵力有限，认为机会难得，就有意挑起叛乱，但被张飞提前发现，把曹豹杀了。
曹豹虽死，但叛乱未停，下邳国大乱。袁术知道消息，派人秘密给在小沛的吕布送去一封信，让他趁机夺取下邳，进而占领徐州，抄了刘备的后路。
袁术写给吕布的信保留在《英雄记》一书中。袁术对南阳郡的不愉快只字不提，反而大大吹捧吕布，说他立下了三件大功，分别是诛董卓、袭兖州、帮助自己破刘备。
吕布在张邈、陈宫的帮助下从背后下手袭取了曹操的兖州，这件事在袁术看来是正义的行动，他的理由是，当时朝廷正式任命的兖州刺史是金尚，他到兖州上任，结果被曹操打跑，是吕布为朝廷主张了公道（复明目于遐尔）。
其实这有点东拉西扯，袁术起兵的时候恐怕并没有想过自己的身份是否合法，他还扣留过朝廷的特使，随意任命官吏。现在，就连朝廷都变得很务实了，已经正式任命曹操为兖州牧，袁术还旧事重提，实在是相当无聊。
不过，袁术的目的是吹捧吕布，跟他拉近乎。袁术说完吕布三大不世之功以后，紧接着开出了双方合作的条件，袁术请吕布拿出当年袭取兖州的劲头再袭取徐州，为此他愿意为吕布提供二十万斛粮食，而且说明这仅是第一批，以后还会源源不断，至于兵器战具，要多少有多少（它所乏少，大小唯命）。
吕布接到袁术的信，大喜过望，立即整军出发，直奔下邳。
据《英雄记》记载，吕布奔袭下邳不仅带来了步兵和骑兵，还有一支新军：水军。这应该是吕布到小沛后新组建的部队，这支水军行进的路线应该由泗水河南下而来，因为小沛和下邳城都在泗水河畔。
吕布率水陆两军在下邳城以西四十里的地方会合、驻扎，张飞手下的中郎将许耽悄悄派出一个叫章诳的团长（司马）来见吕布，表示曹豹被杀后，城里大乱，丹阳兵决定反攻刘备，他们有一千多人控制了下邳的西门，可以里应外合。
许耽是丹阳郡人，是陶谦的老乡，此人可能跟曹豹一样，是陶谦的旧部。吕布得信大喜，连夜进军，到达下邳城西门。此时天刚亮，负责守卫此门的丹阳兵果然打开城门，迎接吕布入城。
下邳城当地人称西门为白门楼，这是一个跟吕布有缘的地方。吕布此时登上城楼，坐在上面指挥城内的巷战。张飞不是对手，落荒而逃。吕布把刘备的妻小以及刘备手下各位将领的家眷全部俘虏。
整个事件进行得很顺利，吕布是受益者，袁术的受益更大，让人不由怀疑从曹豹到许耽都是袁术精心策划的，加上吕布的配合，让事情进展得出奇顺利。
在前线作战的刘备闻知此讯如五雷轰顶，他顾不上袁术，立即回师下邳，但手下人知道眷属们都在吕布手里，无心作战。刘备看到没有获胜的希望，只好带着人又南下，与袁术作战，但被击溃。狼狈不堪的刘备一直退到广陵郡的海西县，此地大约位于今江苏省灌南县，如今是内陆，而在当年则是沿海。刘备再退就得到海里当渔民去了。当时城里严重缺粮，官民甚至相残，出现人吃人的惨象。
在这个最艰难的时刻，刘备手下的从事麋竺给了他最大的支持。麋竺是徐州刺史部东海郡人，是陶谦的旧部，对刘备很看好。麋家世代经商，是当地的富豪，麋竺和兄弟麋芳散尽家财支持刘备，同时集合了仆人、宾客和族人共两千多人加入到刘备的队伍中。不仅如此，麋竺还把自己的妹妹嫁给刘备当夫人。刘备在小沛时娶的当地人甘氏，此时已落入吕布手里。
麋竺在刘备事业最低谷的时候倾全力支持刘备，看得出来他很有眼光。麋竺此后一直追随刘备，深得刘备信任，是商人从政的成功代表。
虽然有麋氏兄弟的大力支持，刘备暂时可以不当渔民，但前途仍然黯淡。在走投无路之际，他做出了一个让所有人都觉得不可思议的决定：投降吕布。
这件事要换成袁绍或袁术，那是宁死也不会干的。换成是曹操，估计也够呛。但吕布能做出来的事，刘备也能做出来，在别人看来不可能的一件事，恰恰成了最现实的问题解决方案。吕布听到刘备来降，慨然接纳，不仅把俘获的刘备及手下人的家眷全部归还，还给刘备找了一个好地方，安排了一份好工作。
想必大家已经猜出来了，这个好地方就是小沛，这份好工作就是豫州刺史。
吕布的逻辑跟之前的刘备以及刘备之前的陶谦都一样，把刘备放在敌我之间的缓冲地带当盾牌使。吕布自称徐州牧，表奏刘备为豫州刺史，二人的职务来了个乾坤大挪移。这样，徐州的局面总算暂时稳定了下来。
对曹操而言，刘备和吕布都是不能掉以轻心的对手，这两个人如果团结起来，问题更麻烦。现在，他们出现了内讧，相对容易对付的吕布又暂时得势，这不失为一个好消息。