南越國不過是漢帝國南方小小的一隅，然而在劉恆眼中，它卻成為了自己樹立威望的道具。誰都清楚，南越人無意挑釁漢朝，漢朝人更不是滅不了南越。但不巧的是，這個小國家卻和帝王的名譽掛上了鉤。劉恆急需通過招降南越，來樹立自己的威名。
蔡東藩有首《贊漢文帝懷柔趙佗》詩，詩云：「武力何如文教優，御夷有道在懷柔。詔書一紙蠻王拜，伏地甘心五體投。」（《前漢演義》第四十七回）詩的內容很白話，講的是南越王趙佗向劉恆稱臣，然而這首詩背後卻有一個不簡單的故事。
秦朝統一六國之後緊接著平定了楊越地區，設置了桂林郡、南海郡和象郡。這三個郡荒涼落後，對當時的人而言，絕對算得上是窮鄉僻壤，因而成為了秦朝罪犯、官員的流放之地。流放至此的罪犯們與越人雜居，生活了十三年。
秦朝末年，南海郡郡尉任囂病重。郡尉本來是郡守的副職，掌軍事，但是由於南海郡蠻夷太多，民風彪悍，加上平定不久，所以一直是讓郡尉當一把手，由軍事長官將軍政大權「一把抓」。
任囂病重期間念及自己時日無多，知道此時天下大亂，因而找來了手下心腹龍川縣令趙佗，對他說：「中原大亂，群雄逐鹿，不知道什麼時候能安寧下來。現在已經有不少人脫離秦朝統治而自立了。我本來打算派兵切斷和中原的聯繫，等待時機大展雄圖，然而如今我病重了，保衛不了咱們這個地方。番禺靠山面海，地域廣闊，還有不少漢人智者可以幫我們，弄好了還可自立為一方之主，建立國家。郡里的官吏都不可信，我才叫你來，將這些事情託付給你的。」說完，任囂寫了一張委任狀，讓趙佗代理南海郡尉。
沒過多久任囂就撒手人寰，他死後，趙佗立刻下令派重兵扼守橫浦關、陽山關、湟溪關三處重要關隘，同時斬殺了過去秦朝在當地的一些官吏，全部安插了自己的親信。
秦朝滅亡之後，趙佗吞併了桂林郡和象郡，關起門來當地頭蛇，自立為南越武王，稱霸一方。
漢高祖平定天下之時，按照《史記·南越列傳》的說法，劉邦不願意再讓百姓經受戰亂，所以才沒有征討南越國。然而，從劉邦在高祖十一年（公元前196年）才派遣陸賈出使南越國來看，劉邦在立國初期不處理南越國的問題主要是因為兩點。
第一，劉邦壓根沒有重視南越國立國的問題。「布衣天子」聽起來很親民，但總免不了會有些目光短淺的毛病。劉邦的短見及其危機意識的缺乏，最終直接導致了趙佗勢力的坐大。
第二，此時的國內內亂繁多。政治鬥爭和平叛早已經讓劉邦忙得不可開交，加之北邊還有匈奴的威脅，他哪裡顧得上南邊的蠻夷呢？而且劉邦在統一天下後還解散了許多軍隊，士兵數量大減，趙佗在南方僻遠之地建國，劉邦實在無力分兵前去征討。
然而問題總歸是要解決的，陸賈的出使成功說服了趙佗歸順。劉邦與趙佗交換了符節，要求趙佗在南越地區處理好民族關係、同長沙國政府積極往來、和當時的長沙王吳芮搞好關係。
劉邦能夠答應這樣沒什麼「油水」的議和條件，無疑是展現出了一種求和的姿態。劉邦到最後還是沒能力對南越動武，可見漢初整個國家在飽經戰亂後國勢的衰微。好在南越民風淳樸，少數民族嘛，剽悍是剽悍，但那是人家性子直，反過來講，就是講義氣好說話知恩圖報懂得大義，所以南越才會同意歸順。
然而，歸順的行為終究是南越人主動的，劉邦只是拋出了橄欖枝，趙佗原本可以不接。這就意味著，在南越人的心中，他們自己都一直處於優勢地位，習慣上還是覺得自己比漢朝人厲害一等。所以在呂后時期，一遇到漢朝在鐵器方面的封鎖，他們就反叛了，而且認為是長沙王吳右（吳芮曾孫）為了滿足自己擴張疆域的欲求而挑唆呂后做的。
於是憤怒的趙佗不稱王了，直接自稱為南越武帝，發兵攻打長沙國，連敗長沙國數縣。呂后聞後大驚，派隆慮侯周灶帶兵征剿，結果水土不服導致了軍隊中瘟疫流行，士兵上吐下瀉，漢軍只好作罷。
公元前180年七月，呂后駕崩，趙佗趁機發展勢力，收買了閩越王無諸的閩越國、廣西地區的西甌國、越南北部的駱越國。這一下，南越帝國的疆土東西長達萬餘里，疆域大增。趙佗也洋洋得意起來，用起了佩有黃屋左纛的車馬儀仗，儼然一副中原皇帝的氣象。趙佗要求漢朝將長沙郡劃歸南越國境內，這些行為處處顯現出挑釁的意味。
到了文帝前元元年（公元前179年），南越國已經成了一塊燙手的山芋，然而劉恆卻並不著急，劉恆正嫌沒地方展現他的才能、樹立他的威信呢，趙佗越活躍，劉恆越高興。雖說派兵剿滅南越國不是什麼難事，但劉恆是為了宣傳新政，要以德服人。所以劉恆做了兩件事來為他以德服南越國做鋪墊：
第一，派專人保護趙佗父母位於真定的墓，並按時祭祀；
第二，將趙佗在老家的兄弟們都封以高官，賞以厚祿，表示對趙佗的尊寵。
在處理趙佗的問題上，劉恆針對的不單單是南越國一個國家。他是借處理趙佗的問題，來給所有的異姓諸侯王國和少數民族地方勢力做出一種姿態，一種寬容、大度的姿態，借之收買人心，來樹立這些諸侯王、少數民族以及老百姓對他的信心，讓人們相信他能夠擺平王國問題和民族問題這兩件事。
在陳平的推薦下，劉恆再次派遣陸賈出使南越國，隨行帶有劉恆的書信，也就是勸降書一類的物品，信中說道：
「漢皇帝誠摯地問候南越王。我不是高皇帝嫡出的兒子，後來被封到代國，那地方離南越國太遠了，而且那時候我還年輕，見識淺薄，所以一直沒有和南越國聯繫。
「高皇帝死得早，孝惠帝也沒活幾年就駕崩了，呂后後來稱制，但她的身體一直不太好，所以有時候想事情半天轉不過彎。呂家人比較蠻橫，拿假冒的劉氏後裔繼承孝惠帝的皇位。好在神靈保佑，呂氏家族已經被功臣們幹掉，大漢重新安定。
「前幾天看見您讓隆慮侯轉交的書信，讓我找到您的兄弟並撤回攻打您的軍隊。我現在全都照辦了。以前聽說大王您老騷擾我們的邊境，搞得長沙國和南郡雞犬不寧，我就想啊，這對你的國家有什麼好處？不過是死更多的士兵，讓更多的將領殘疾，弄出更多的寡婦孤兒和留守老人罷了，這就叫『得一亡十』，我實在不忍心。
「我打算把南越國周圍的那些土地都贈送給您，可是有人給我說那都是高皇帝安排的，我也改不了。有人說你那塊地方對我們漢朝而言並不大，不如全讓你管算了。雖然大王您已經稱帝了，但兩帝並立，總需要有個使者聯絡聯絡感情，好歹您也提前知會我一下呀。所以我讓陸賈跑來，您要是答應我們的條件，就別再來騷擾我們的邊境了。我這裡有五十件厚棉衣、三十件中等棉衣、二十件薄棉衣給您，希望您忘卻憂患，好好享樂，順帶問好閩越國、西甌國、駱越國。」
仔細分析劉恆的書信，首先是姿態放得很低，畢竟劉恆是在賭趙佗會投降，他要利用趙佗的投降樹立威信、聚攏人心，所以必須放低姿態來增大議和成功的概率。
其次是不攬任何實際責任，消除趙佗和自己的芥蒂。不管什麼措施和建議，只要是讓趙佗不高興的，那都是劉邦、呂后和群臣們乾的。
三來如果趙佗有心議和，劉恆的姿態這麼低，那他趙佗應該更低才是，那就更能滿足劉恆追求名譽的想法了，讓南越國在和漢朝的交往中處於絕對的弱勢，這是劉恆心裡的小九九。
趙佗本來就知道自己終究是不可能戰勝漢朝的，他不過是「以戰求和」，看到劉恆的書信之後趕緊借坡下驢，於是回信說道：
「南方蠻夷的首領趙佗問好漢皇帝。當年呂后欺負我們南越人，不賣給我們鐵器，我懷疑這是長沙王說了我們南越人的壞話，加上後來又聽說呂后把我一家子全殺了，還挖了我家祖墳，所以才斷絕了和漢朝的來往，攻入了長沙國的邊境。
「至於稱帝這件事，那是皇上您不了解情況，我們這裡的閩越國、西甌國、駱越國等原始野蠻國家的頭領都稱了王，我想管著他們，所以不能一個叫法。但由於臣沒文化，也起不來別的名字，所以才稱帝，不過也就是自己玩玩，哪敢跟皇帝您正式彙報呢！」
於是趙佗叩頭認錯，並且下詔說：「一槽容不得二馬，兩個英雄不能同時並存，說到底還是人家漢朝皇帝牛，以後我不再稱帝，也不用皇帝的儀仗了。」
劉恆聽完很高興。經過這件事，劉恆的民眾支持率暴漲，因為老百姓都知道，在劉邦時代，諸侯、土酋經常反叛，而他們現在卻都歸降了。這一下，漢朝人的心理優越感逐步恢複了，對劉恆的信任也加強了，國家對未來更自信了。
招降南越國是劉恆在位期間，在處理民族事務上做得最成功的一件事。