無論是司馬遷的《史記。呂太後本紀》，還是班固的《漢書。高後帝紀》，對呂後的籍裏都沒有談及。《史記。高祖本紀》中記：“單父人呂公，善沛令，避仇從之客，因家沛焉。”這位呂公，即是呂後之父。史失其名，舉姓而稱呂公。為《史記》作《索引》的唐代學者司馬貞，引用《漢書舊儀》上的資料，謂：“呂公，汝南新蔡人，”複引《相經》上的記載，謂：“魏人呂公，名文，字叔平。”
那麽，這位撲朔迷離的呂公，到底是山陽單父人還是汝南新蔡人？
後世治史的學者，執此兩端，歧說紛紜。
執新蔡說者，認為司馬貞所引《漢書舊儀》和《相經》上的資料可以坐實，呂公確是新蔡人，明、清《新蔡縣誌》均有記載。近年來出版的《新蔡縣人物誌》分別為呂文和呂雉立了傳，稱其故裏在現河南新蔡縣城關。並且認為呂雉十幾歲時，其父呂文把家搬移到碭郡單父縣，也就是現在的山東省單縣。後又因避仇，遷家到沛縣。研究新蔡地方史的學者謝石華更認為：呂姓的發源地就在新蔡。
新蔡的前身是夏朝初年（公元前2070年）伯夷受封的呂侯國，周惠王三十一年（公元前656年）曾被宋國吞並，周頃王元年（公元前618年）首次淪於楚國。周景王十四年（公元前531年）楚滅蔡國，兩年後，楚國又扶植蔡平侯將臣民遷至呂侯國地盤複國，史稱新蔡。蔡國舊地因在新蔡西北部，被稱作“上蔡”。蔡昭侯二十六年（公元前493年），蔡昭侯懼楚，東遷吳地州來邑（現在的安徽鳳台縣下蔡鎮），改州來為“下蔡”，呂侯國地重歸楚國所有。原新蔡都城改稱新蔡邑。
楚考烈王七年（公元前256年），秦滅周，結束戰國時代。秦王政二十三年（公元前224年），秦占領淮河、泗水以北大部分地區，改新蔡邑為新蔡縣，這是新蔡建縣之始。並與淮泗以北的相縣（今安徽靈壁北）建立了泗水郡。