在成功解除了来自北方的威胁后，刘备松了口气，他可以一心一意的对待淮南袁术了。
幽州公孙瓒、青州田楷自顾不暇，无力报复刘备的背叛。目前真正对他构成严重威胁的只有袁术一人。
袁术被曹操痛扁之后，“以余众奔九江，杀扬州刺史陈温，领其州（治今安徽寿县）”。在据有扬州之地后，袁术毫不掩饰自己对徐州的觊觎之心，自称“徐州伯”。显然，这个自大狂已经将徐州视为自己的禁脔。——（《三国志-袁术传》）
刘备继任徐州牧，是袁术最不能容忍的事情。
就在刘备履新徐州牧不久，吕布率领部众前来投附。当吕布知道刘备是涿县人，而且曾是江湖中人之后，顿生知己之感。
据王粲《英雄记》载，二人初次相逢。
布见备，甚敬之，谓备曰：“我与卿同边地人也，布见关东起兵，欲诛董卓。布杀卓东出，关东诸将无安布者，皆欲杀布耳。”
请备于帐中坐妇床上，令妇向拜，酌酒饮食，名备为弟。
备见布语言无常，外然之而内不悦。
人在屋檐下，不得不低头。心高气傲的吕布也得遵循“强龙不压地头蛇”的江湖规矩，对徐州地主表现出应有的尊重。而且先是与刘备套起了近乎，首先告诉刘备，兄弟我也是苦大仇深的草根。继而，“自以为对革命有功”的他言辞闪烁的道出了自己的窘境（寄人篱下的滋味不好受！说这番话的时候吕布如果虎目含泪的话，那么更煽情。）之后，吕布又唤出了妻子拜见刘备，自备酒水招待刘备。
吕布这样做，明显是在向刘备示好。人在旅途，不可能背负了房屋走路，“令妇向拜、酌酒饮食”也是从权之举。虽然汉时的男女之防很是注重，但吕布以为刘备与自己一样是江湖儿女，并不会在意这些。这样以家人礼见面更显得亲密无间。
史实证明，先入为主害人不浅：
此时的徐州牧刘备，已经远非从前的涿县刘大耳朵。这时候的他内心深处时刻提醒自己要保持正襟危坐的模样，端起正人君子的架子了。吕布表现出来的江湖气息更是令他难以忍受，好不容易成功洗白的他决心忘记从前的不愉快，最忌讳人们提及他卖草鞋、收保护费的往事。
现在吕布和他“忆往昔峥嵘岁月稠”，只能令他觉得吕布此人“语言无常”。
虽然吕布痴长他两岁，但也不能就妄自尊大啊！
“玄德兄弟”是你叫的吗？
吕布真不把自己当外人啊！
刘备“外然之而内不说”（说、悦也），实在是顾忌吕布功夫了得，飞将军自重霄入，关于吕布的传奇刘备早有耳闻。可以和曹操周旋一年有余的对手，同样令他敬畏。（拍马也是门学问，吕布的赤兔马通人性，所以吕布不谙拍马之道。现在一不小心拍在了驴屁股上，没有出现“驴不胜怒、蹄之”的后果已经是万幸！）
虽然刘备心中像吞了只苍蝇一样，但也无力回绝吕布的避难请求。自己急公好义的名声在外，现在吕布落难来投，拒之门外将有损声誉。最主要的原因是吕布不请自来，刘备这个东道主无力抗拒。刘备没有付诸武力解决，并不是担心胜之不武，而是怕搬起石头砸了自己脚。万一弄巧成拙，徐州地方好不容易构建的安定祥和现状就会打破。
刘备与吕布和则两利、斗则两伤，二人一样，刘备也是外来务工者。不过比吕布早到些时候而已。吕布为陈宫张邈等人迎为兖州牧的事情，时刻提醒着刘备：害人之心不可有，防人之心不可无！
建安元年（196年），三十六岁的刘备流年不利。
树欲静而风不止——徐州在经历了短暂的安宁之后，重新陷入了新的一轮动荡。刚刚安顿好吕布的事情，袁术就率领手下打上门来。
袁术不宣而战，刘备不敢怠慢。他安排张飞守下邳，自己统率部众前往盱眙、淮阴迎敌。双方相持月余，互有胜负。袁术既不能寸进，刘备也无力退敌。正在胶着难下时候，从大后方传来惊人消息：
下邳失守！