萧何在沛县任主吏掾时，沛县有一位神秘人物，民间有关他的传说有很多。这个人虽然只是一介平民，但是在当时的沛县，黑白两道的人都很服他。他就是刘邦。
说刘邦这个人神秘，是因为有关他的传说有很多，而且传得很玄乎，包括他的长相，很多人都认为他的长相与众不同。据司马迁在《史记？高祖本纪》中所载：“高祖为人，隆准而龙颜，美须髯，左股有七十二黑子。”这段话是说刘邦不仅长得好看，而且身上有不少异相，所谓“隆准”，就是指鼻子高挺，两颊端正；“龙颜”是指刘邦的颈子很长，胸部挺直，背脊硬朗，手脚长而有力，在众人中显得鹤立鸡群，相当有精神；美须髯是指他的胡子特别漂亮，看起来显得特别高贵，少年老成；尤其让人不可思议的是他的左大腿上有72颗黑痣。在中国古代相学中，72是个大吉大利之数。一些喜欢讨论异相的三姑六婆，得知刘邦的体型与长相与众不同，便一传十，十传百，百传干，结果很快就传遍了沛县。
这还不算玄乎，因为如果一个人的长相确实是这样，那么大家都可以亲眼看见，能够亲眼看见的东西说不上玄乎。对于刘邦来说，传得更玄乎的事还在后头。据说，当时刘邦经常到王媪、武负家赊酒喝，有一次，刘邦喝醉了，就在他们家睡下，王媪和武负居然发现刘邦的身上有龙出现，感到很奇怪，觉得刘邦绝非凡人。这两个人平常都是以高价把酒卖给刘邦，自从他们看到刘邦身上的这一奇异现象后，就再也不要他的高价了，并且到了年底干脆销毁了账簿，不再向刘邦要欠下的所有酒钱。
当然，在沛县关于刘邦的传说远远不止这些，这样的传说多了，很多人都开始对他另眼相看起来。再加上他这个人为人慷慨大方，在市井上有一帮狐朋狗友为他前后吆喝，跟在他旁边起哄的喽哕也越来越多。他不仅生性豁达，而且很爱“面子”，为了面子，什么事都可以答应下来，许多人都喜欢与他打交道。因此，他虽然只是一介平民，名气却比那些官员要大得多。当然，由于三教九流的人都愿意与他结交，他与这些人混在一起也免不了要闹出一些事来，而且这样的事还不少，拿我们今天的话来说，像他这样的人在当地派出所里应该是挂了号的，算是问题人物。但是，令萧何想不到的是，与他同衙共事的曹参是沛县的狱掾（相当于我们现在的县公安局长），是专管县中的问题人物的，可是他不但不去收拾刘邦，甚至还经常和刘邦混在一起。尤其是那个夏侯婴，他先前在县衙负责管理县府的马匹，为县令驾车（相当于现在的县长大人的专职司机），现在已升为试补县吏，也算是沛县有头有脸的人，但这家伙对刘邦硬是服气得很，几乎逢人便说刘邦这人不错、很好。萧何问他，大家都说刘邦这个人很神，你逢人便说他好，难道他是圣人，比尧舜还厉害？
这夏侯婴是个爱开玩笑的人，不过他回答萧何的话并没有开玩笑，他说：“我要是说他是圣人呢？你不信；我要是说他比尧舜还厉害呢？你说我是在吹牛。这样吧，你哪天去见他，你见了他就知道他是什么人，你见了他就知道他为什么有这么大的名气，有这么多人服他。”
这萧何一听有些不信，就让夏侯婴找时间带他去见识一下这位神秘人物。
果然，过了几天，夏侯婴便带萧何去见刘邦。见了刘邦，一阵闲聊以后，他明白了像曹参、夏侯婴这帮人为什么服刘邦了。这刘邦你不能说他是圣人，也不能说他是尧舜，但你见了他，你会觉得他绝对不是一个平凡的人。他说不上是君子，甚至对人有些傲慢无礼，但你几乎不会因此去排斥他，他似乎天生有一种魔力，很多人在他面前都会觉得自己要比他矮三分。萧何见了刘邦也服了，就像后来的张良见刘邦那样，简直就是一见如故。从此，萧何也成了刘邦的一党。刘邦在沛县的影响越来越大，在他的周围云集了一大批沛县中的精英分子，三教九流、各色人等，应有尽有，而且只要刘邦打一声招呼，这些人就会立即照着他的意思去办。这个以刘邦为中心的组织，被沛县父老称为“刘季党”。如果用我们今天的眼光来看，刘邦的这个组织可以被定性为黑社会组织，刘邦就是这个组织的头目。刘邦有时犯了事，只要不是天大的事，在县衙的萧何、曹参、夏侯婴等人自然要想办法为他开脱。
当时，秦朝的法律非常严酷，交通又不便利，一些地方官员觉得要管理好一个地方非常不容易，于是，他们也常常借助于地方上一些有声望的在野人物协助管理。沛县也是如此。在沛县，县衙里有不少官员都喜欢跟刘邦打交道，遇到麻烦事时，更喜欢找刘邦帮忙，刘邦也乐于效劳，因此，刘邦的人脉基础在沛县非常深厚。当时，天下已经有了纷乱的迹象，萧何认为像刘邦这样的人，很可能会成为乱世中的英雄。萧何是主吏掾，是负责人事和文书工作的，于是他向县令推荐刘邦当泗水亭的亭长。由于县衙里的不少官员都已经跟刘邦打成了一片，所以对他的面试考核也就是走一道程序而已。刘邦就这样当上了泗水亭长，成了公门中的人。
不过，刘邦并没有因为自己成了公门中人，而对自己傲慢无礼、放浪不羁的一面有所收敛，县衙里几乎所有的官员都受过他的侮辱或调侃。为此，有一次，他和夏侯婴比剑玩时，一不小心把夏侯婴伤了，有县吏为了报复他便向县令密告，说刘邦故意伤害官差。
刘邦身为亭长，却伤害朝廷官差，不但会被革职，还要被判处重罪。由于夏侯婴主动愿意替刘邦背黑锅，始终不承认是刘邦刺伤了他，刘邦才免于被处罚。但夏侯婴却为此挨了数百下鞭子，并被打入大牢，判处一年刑狱。
然而，不管刘邦对其他县吏的态度怎么样，他对萧何从见面的那一天起，就一直非常尊重他，有什么事都会主动和他商量，并经常对萧何说：“好吧！反正听你的就是了。”刘邦这股相信人便信到底的豪劲，使萧何对他非常倾心，这是他后来愿意追随刘邦博弈天下的重要原因。在萧何的眼里，刘邦的所谓傲慢无礼并不是什么缺点，只是他的一大特点，他认定这个人将来能干大事，所以总是对他另眼相看。由于刘邦的朋友多，喜欢应酬，爱面子，所以手头经常有些吃紧，出现财政困难，萧何常常拿出自己的俸禄资助他。有一次，刘邦去咸阳出公差，大家都知道出远门要花钱，纷纷资助刘邦，沛县县衙里的那些官员资助刘邦的都是三百钱，惟独萧何资助了刘邦五百钱。刘邦去咸阳办完事后，拿着这些钱在咸阳城四处闲逛，去歌楼妓馆逍遥快活了一番。一天，他在咸阳大街上看到秦始皇出巡的队伍，望着庞大的仪仗队和护卫队，看到秦始皇的赫赫威仪，他由衷感慨道：“嗟乎，大丈夫当如此也。”也许正是从这个时候开始，他萌生了发誓要做皇帝的念头。