刘备在糜竺的推荐下出任徐州牧，又在糜家鼎力支持中迅速稳定徐州局面，刘糜联姻，紧密合作，伤害了许多人的利益，让原本拥立他为徐州之主的各个派系产生深深的不满。
这个时候曹操与吕布的兖州之争已经分出胜负，战争进入了尾声，张邈被杀，吕布也被曹操赶到了东平。吕布退至泰山郡，他在陈宫建议下，派兵前往济宁，泰山险关隘道驻守，据险与曹军周旋，曹操一时之间还真拿吕布没办法。泰山将臧霸，陶谦旧部曹豹不满刘备忘恩负义，遭到他的抛弃背叛，派人密密联络兖徐边境上的吕布，共同对付刘大耳，拥护他吕布做徐州之主。
吕布、陈宫在军帐中接见了臧霸的使者，两人从使者口中得知徐州现在的状况，觉得大有可为，于是答应与臧霸、曹豹联合，先到徐州立足。吕布带领手下万余残兵进入徐州彭城国，投奔在下邳的刘备，他见到刘备后，对其非常尊敬，态度十分诚恳，姿态也放得很低，向刘备拱身见礼，：“玄德公，你我同为北方边境之人，今日来投还望公不弃收留。初平年间我见关东诸军起兵，誓要诛杀董卓，然而我顺天应人斩杀董卓东出，关东诸将却没有一个人肯接纳我，还都想要杀了我。想我吕布一世英明，却落得个无处安身的下场。”
刘备将吕布迎入下邳城，他被吕布的言语触动，想他磋砣半生，几乎是上无片瓦挡雨，下无半缕遮身，穷困潦倒，没有半寸立足之地，狼狈如丧家之犬无处容身，，东奔西走如无家可归的游浪汉，食人牙惠。幸是机缘巧合，他才得有徐州用以立足，刘备思之至此，同病相怜，同是英雄豪杰却遭人嫌弃，难得重用，他十分同情吕布。后来酒席间吕布吩咐其妻妾向刘备行礼敬酒，酌酒侍候饮食，这让刘备同情心开始泛滥，他安排吕布到小沛驻守。
吕布按照刘备的安排到小沛驻军，陈宫建议吕布将万人分布两部，五千人在小沛城内负责城防治安，曹性为巡城官，另外五千人由郝萌、魏续、宋宪、成廉、侯成五人统领在城外驻守。
刚到徐州安顿不到两个月的吕布收到献帝的诏书，要他率军前往潼关迎驾。兴平三年十二月，因李傕、郭汜因意见不合发生火拼，汉献帝欲借机从长安东归，下诏书令吕布迎驾。吕布已至徐州，路途遥远，于是他派遣使者随同传诏宦官回到长安，以军队没有足够粮草，山高路远，寄人篱下，无法擅自动兵勤王为由上书谢罪。汉帝不光没有等到吕布勤王之兵，还得升赏他，表彰他的忠义之心，朝廷任命吕布为平东将军，封平陶侯。
朝廷使者到小沛宣布对吕布的任命，下邳城里的刘备等人也得到消息，糜竺乘机在刘备耳边说吕布坏话，称他背恩诛董卓，忘义杀丁原，是个十足的小人，应尽快驱赶出徐州地界，免得以后成为祸患。陈登也向刘备进言道：“吕布先投袁术，袁术不满他恃功自傲，行事十分骄横、纵兵抢掠，将其拒之门外。吕布又改投袁绍，他依仗着自己的战功，向袁绍要求增加军队，袁绍不许，而吕布放纵手下的将士抢劫财物、掠夺粮食，强拉壮丁，引起袁绍记恨，欲除之而后快。吕布稍施小计脱难而出入兖州，又将兖州搅得天翻地覆。大人宜早日除之免遭后患。”陈登之所以这时候添油加醋，旨在挑起吕刘争斗，让曹操坐收渔翁之利。
刘备不纳忠言，让吕布继续留守小沛坚持己见，认为吕布私德有缺，但不至于忘恩负义，犯上作乱，背叛自己，祸害自己的徐州。
建安元年（196）袁术率军攻打徐州，袁术始终将徐州当作自己的后花园，他还自称徐州伯，徐州又是幽青徐扬联盟中的重要环节，是对付袁绍的桥头堡，现在被名不见经传，冒充皇叔身份，爱哭鼻子的刘备占领。他十分恼火，刘备何德何能敢占据徐州牧的高位，认为其不配拥有这块富饶之地。袁术发兵十万，征讨刘备欲夺回徐州，双方大军对峙在盱眙、淮阴。相持一个多月，袁术和刘备互有胜败。袁术谋士阎象提出建议，对袁术道：“主公，情况大为不妙，我们是长途奔袭，而刘备是本土作战，如此对峙天长日久对我方不利，照这样下去我方粮草运输供应必然出现问题，到那时一切将功亏于溃。我们应该尽快结束战争，否则迁延日久就算拿下了徐州也是个劳民伤财，两败俱伤的局面。现在即然正面难有突破，那就从内部瓦解他们，听闻吕布新附于刘备，我们可从他身上作些文章，耍些手段，许以重利，让吕布从背后偷袭骚扰刘备，介时正面不攻自破。”
袁术听从阎象建议，于是写信给吕布，信中表示愿意送上二十万斛粮食以为军资，并且承诺事成之后平分徐州，诱使其袭击下邳。陈宫抓住这个机会对吕布劝说：“将军，当今天下四分五裂，英雄倍出豪杰并起，您拥有近万名精锐的铁骑部队，又处于徐州这个战略要冲之地，你本英雄奈何气短，寄人篱下，仰人鼻息，何不乘此机会按剑雄视天下，挥斥方酋，打下一片天地，得到数万带甲之士，到那时将军岂不是天高任鸟飞，海阔鱼任跃，飞龙在天。”
吕布被袁术诱惑到了，又被陈宫劝动，于是他紧急联络曹豹、臧霸，三人一拍即合决定趁着刘备在前线与袁术对峙，武力夺下徐州赶刘备下台。吕布、臧霸率军水陆并进，军队到达下邳西四十里时，刘备的中郎将丹阳人许耽派司马章诳前来接应吕布，并向吕布透露了张飞和曹豹不合暗中争斗的信息，眼下下邳城内大乱，丹阳士兵都在西边白门楼城内等待着吕布的到来。吕布得知情况后率军快速前进，清晨时刻便抵达下邳城下。
天色完全放亮，丹阳兵打开城门，曹豹、许耽接迎吕布入城。吕布、陈宫随后吩咐封闭四方城门，指挥军队围剿忠于刘备的残兵，吕布亲自上阵对战张飞，张飞宿酒未醒，见是吕布夺了城池，十分愤怒指着吕布鼻子大骂：“吕布，你这个三姓家奴，你这个狗东西，你这个白眼狼，我大哥好心好意收留你，你却忘恩负义，背后捅刀子，唵老张今天定要活剐了你这天杀的。”
吕布与张飞在马上对战了三十回合，戟来矛往，双方均惊叹对手的武力高强，张飞的酒惊醒了，吕布也认真起来，张飞是他自与秦锋交手后遇到的第一高手。吕布又与张飞交手二十回合，张飞险些失手被擒连忙拨马杀向城门冲出城去，吕布念及刘备恩义没有让人去追。
吕布带人进入牧府，俘虏了刘备的妻妾及其部曲的家眷，吕布没有欺辱他们，只是软禁众人在一个小院落里，限制他们的行动自由。张飞逃到城外只身直奔盱眙前线找到刘备，向他哭泣吕布忘恩负义，狼子野心。刘备得知下邳丢失，懊悔当彻没有听从陈糜之言，终成大祸。下邳被夺的消息在有心散播和宣染下，很快军中传开，将士们得知后方下邳丢失家属被俘，顿时军心浮动，士气低迷。不久后刘备为袁术所败，率领残兵逃往海西，粮食紧缺，众人饥饿疲惫，孙乾建议刘备向吕布请求投降以图后手。
张飞听到孙乾之言，恨不得拔出刀剑砍杀他，幸好被糜竺劝住，谋士简雍也赞成孙乾所说。刘备见众谍士皆赞同孙乾提议，他豁出去，大丈夫能屈能伸，高祖刘邦、越王勾践、兵仙韩信都能受辱负重，况且投降依附他人。袁术见吕布成功夺得下邳，便不再运送粮食给他，吕布十分恼火，他就接受了刘备请降，并且准备了车马迎接刘备，还让其担任豫州刺史，派他驻守小沛，送还刘备军妻子家小。
这样以来徐州原先刘主吕从的局面变成了吕主刘从，现在形势完全颠倒过去，最初的徐州由三方势力变成四方势力，现在由于吕布和袁术的加入，已经有了六股势力，将来曹老板再来插一脚，那就热闹，只怕徐州再难稳定，目前吕布势力和丹阳派、泰山诸将占主导地位。
建安元年（196年）六月夜半时，吕布部将河内人郝萌在袁术的挑拨、怂恿下发动叛乱，他率兵攻打吕布治所下邳，城池防守坚固短时内无法攻入，吕布不明情况也不知道造反者是何人，于是带领家眷逃到宋宪营寨，宋宪问道：“将军可知造反者是谁？”吕布回答：“不知是谁，但这些人皆是河内口音。”宋宪便已经猜到造反的是郝萌，于是率部到平叛，与城中守军内应外合，弓弩齐发射杀郝萌军，天亮战斗结束斩杀郝萌还营。战场上下邳巡城使曹性对战郝萌，郝萌刺伤曹性，曹性也斩断郝萌一臂，宋宪刚好赶到乘势斩下郝萌的首级，又让士兵用担架抬着受伤的曹性前往见吕布。
吕布向问起曹性此事缘由，曹性回答：“郝萌受到袁术的鼓动而造反。”
吕布又问：“可有同谋？”
曹性回答说：“有，陈宫是同谋。”当时陈宫就坐在吕布旁边，没有出声辨解，只是脸色有些发红，旁边的人都察觉到了。陈宫是吕布的谋士军师，并没有在此事上深究，但这件事也埋下吕布不再对陈宫言听计从的种子。
曹性继续说：“郝萌造反时曾劝我投降于他，献出下邳城。我说大将军神勇，不可抗拒，劝其莫要自误，快快退去，没想到郝萌冥顽不灵，背主求荣，以卵击石对抗将军神威，最后落得到个人头落地的悲惨下场。”
吕布夸赞曹性道：“你乃是我并州的好健儿，真汉子也！”又嘱咐其下去好好养伤，吩咐随军郎中好生照料。
吕布随后回归了下邳，此次挫败了袁术的阴谋，稳定了他对徐州的统治，震慑了一些不安分份子，同时吕布开始怨恨上了袁术。