《晋书·刘元海载记》：“吾每观书传，常鄙随陆无武，绛灌无文。” 随，即指随何。

《史记·高祖本纪》简短地提到了随何，而《史书·黥布列传》记载随何的事迹较为详细：

汉三年，汉王击楚，大战彭城，不利，出梁地，至虞，谓左右曰：“如彼等者，无足与计天下事 。”谒者随何进曰：“不审陛下所谓 。”汉王曰 ：“孰能为我使淮南 ，令之发兵倍楚，留项王于齐数月，我之取天下可以百全 。”随何曰 ：“臣请使之 。”

乃与二十人俱，使淮南。至，因太宰主之，三日不得见。随何因说太宰曰：“王之不见何，必以楚为强，以汉为弱，此臣之所以为使。使何得见，言之而是邪，是大王所欲闻也；言之而非邪，使何等二十人伏斧质淮南市，以明王倍汉而与楚也 。”太宰乃言之王，王见之。随何曰 ：“汉王使臣敬进书大王御者，窃怪大王与楚何亲也 。”淮南王曰 ：“寡人北乡而臣事之 。”随何曰：“大王与项王俱列为诸侯，北乡而臣事之，必以楚为强，可以托国也。项王伐齐，身负板筑，以为士卒先，大王宜悉淮南之众，身自将之，为楚军前锋，今乃发四千人以助楚。夫北面而臣事人者，固若是乎？夫汉王战于彭城，项王未出齐也，大王宜骚淮南之兵渡淮，日夜会战彭城下。大王抚万人之众，无一人渡淮者，垂拱而观其孰胜。夫托国于人者，固若是乎？大王提空名以乡楚，而欲厚自托，臣窃为大王不取也。然而大王不背楚者，以汉为弱也。夫楚兵虽强，天下负之以不义之名，以其背盟约而杀义帝也。然而楚王恃战胜自强，汉王收诸侯，还守成皋﹑荥阳，下蜀﹑汉之粟，深沟壁垒，分卒守徼乘塞，楚人还兵，间以梁地，深入敌国八九百里，欲战则不得，攻城则力不能，老弱转粮千里之外；楚兵至荥阳﹑成皋，汉坚守而不动，进则不得攻，退则不得解。故曰楚兵不足恃也。使楚胜汉，则诸侯自危惧而相救。夫楚之强，适足以致天下之兵耳。故楚不如汉，其势易见也。今大王不与万全之汉而自托于危亡之楚，臣窃为大王惑之。臣非以淮南之兵足以亡楚也。夫大王发兵而倍楚，项王必留；留数月，汉之取天下可以万全。臣请与大王提剑而归汉，汉王必裂地而封大王，又况淮南，淮南必大王有也。故汉王敬使使臣进愚计，愿大王之留意也 。”淮南王曰 ：“请奉命 。”阴许畔楚与汉，未敢泄也。

楚使者在，方急责英布发兵，舍传舍。随何直入，坐楚使者上坐，曰 ：“九江王已归汉，楚何以得发兵？”布愕然。楚使者起。何因说布曰 ：“事已构，可遂杀楚使者，无使归，而疾走汉并力 。”布曰 ：“如使者教，因起兵而击之耳 。”于是杀使者，因起兵而攻楚。楚使项声、龙且攻淮南，项王留而攻下邑。数月，龙且击淮南，破布军。布欲引兵走汉，恐楚王杀之，故间行与何俱归汉。

……

项籍死，天下定，上置酒。上折随何之功，谓何为腐儒，为天下安用腐儒。随何跪曰 ：“夫陛下引兵攻彭城，楚王未去齐也，陛下发步卒五万人，骑五千，能以取淮南乎？”上曰：“不能 。”随何曰 ：“陛下使何与二十人使淮南 ，至 ，如陛下之意，是何之功贤于步卒五万人骑五千也。然而陛下谓何腐儒，为天下安用腐儒，何也？”上曰 ：“吾方图子之功 。”乃以随何为护军中尉。 

白话译文：

汉三年，汉王攻打楚国，在彭城展开大战，失利后从梁地撤退，来到虞县，对身边亲近的人说："像你们这些人，不配共同谋划天下大事。"谒者（负责传达禀报的人）随何近前说："我不明白陛下所说的是什么意思。"汉王说："谁能替我出使淮南，让他们发动军队，背叛楚国，把项王牵制在齐国几个月，我夺取天下的事也就板上钉钉了。"随何说："我请求出使淮南。"汉王就给了他二十人一同出使淮南。到达后，因为太宰作主事，等了三天也没能见到淮南王。随何趁机游说太宰说："大王不召见我，一定认为楚国强大，汉国弱小，这正是我出使的原因。倘若我得以召见，我的话要是说的对呢，那正是大王想听的；我的话说的不对呢，让我们二十人躺在斧头下的砧板之上，在淮南广场上受死。以表明大王背汉向楚之心。"太宰这才把话转告淮南王，淮南王接见了他。随何说："汉王派我恭敬地上书大王驾前的原因，是因为我私下奇怪大王为什么和楚国那么亲近。"淮南王说："因为我面向北以臣子的身份侍奉他。"随何说："大王和项王都列为诸侯，北向而以臣子的身份侍奉他，一定是认为楚国强大，可以把您的国家托付给他。项王攻打齐国时，他亲自背负着筑墙的工具，身先士卒，大王应当出动淮南全部人马，亲自率领着他们，做楚军的前锋，如今只派四千人去帮助楚国。面北而侍奉人家的臣子，难道应该是这个样子吗？汉王在彭城作战，项王还未曾出兵齐国，大王就应该调动淮南所有的人马，渡过淮河，帮助项王与汉王日夜会战于彭城之下。大王拥有万人之众，却没有一个人渡过淮河，这是垂衣拱手地观看他们谁胜谁败。把国家托付给人家的人，难道就应该是这个样子吗？大王实际上是挂着归向楚国的空名，却热衷于依靠自己，我私下认为大王这样做是不可取的。可是，大王不背弃楚国，是认为汉国弱小。楚国的军队即使强大，却背负着天下不义的名声，因为他背弃盟约而又杀害义帝。可是楚王凭借着战争的胜利自认为强大，汉王收拢诸侯之后，回师驻守城皋、荥阳，从蜀、汉运来粮食，深挖壕沟，高筑壁垒，分兵把守着边境要塞，楚国要想撤回军队，中间有梁国相隔，深入敌人国土八九百里，想打，那么又打不赢，攻城又攻不下，老弱残兵辗转运粮千里之外；等到楚国军队到达荥阳、成皋，汉王的军队却坚守不动，进攻又攻不破，退却又逃不出汉军的追击。所以说楚国的军队是不足以依靠的。假使楚军战胜了汉军，那么诸侯们自身危惧，必然要相互救援。一旦楚国强大，恰好会招来天下军队的攻击。所以楚国比不上汉国，那形势是显而易见的。如今大王不和万无一失的汉国友好，却自身托付于危在旦夕的楚国，我私下替大王感到糊涂。我不认为淮南的军队足够用来灭亡楚国。只要大王出兵背叛楚国，项王一定会被牵制，只要牵制几个月，汉王夺取天下就可以万无一失了。我请求给大王提着宝剑归附汉国，汉王一定会分割土地封赐大王，又何况还有这淮南，淮南必定为大王所有啊。因此，汉王敬重地派出使臣，进献不成熟的计策，希望大王认真地考虑。"淮南王说："请让我接受您的意见。"暗中答应叛楚归汉，只是没敢泄露消息。

当时楚国的使者也在淮南，正迫不及待地催促英布出兵，就住在宾馆里。随何径直闯进去，坐在楚国使者的上席，说："九江王已归附汉王，楚国凭什么让他出兵？"英布显出吃惊的样子。楚国使者起身要走。随何趁机劝英布说："事情已到不可回转的地步，可以就此杀死楚国的使者，不能让他回去，然后我们赶快向汉靠拢，协同作战。"英布说："就按照你的指教，出兵攻打楚国罢了。"于是杀掉使者，出兵攻打楚国。楚国便派项声、龙且进攻淮南，项王留下来进攻下邑。战争持续了几个月，龙且在淮南的战役中，打败了英布的军队。英布想带兵撤退到汉国，又怕楚国的军队拦截杀掉他，所以，和随何从隐蔽的小道逃归汉国。

……

项籍死后，天下平定，皇上置酒设宴。皇上却贬低随何的功劳，说随何是腐儒，治理天下哪能用得上这号人呢。随何跪在皇上面前说："当年陛下带领（五十六万人马）攻打彭城时，项王还未曾离开齐国，（那时尚且被项王三万人马打得大败，后来）陛下调动步兵五万，骑兵五千，能凭这点兵力夺取淮南吗？"皇上说："不能。"随何说："陛下派我和二十人出使淮南，我一到，就实现了陛下心愿，这是我的功劳比步兵五万、骑兵五千还要大呀。可是陛下却说我是腐儒，这是什么意思呀？"皇上说："我正在考虑您的功劳。"于是就任用随何为护军中尉。