司马迁在《史记》中曾经使用“南边”一语，用以指代与中原文化系统较紧密地保持一体化关系的与南越相邻的地区。
汉初所置7个异姓王国中，有6个不久就被逐一翦除，只有长沙国得以保留。据说“文王（吴）芮，高祖贤之，制诏御史：‘长沙王忠，其定著令。’”以致“传国数世绝”。“高祖子弟同姓为王者九国，唯独长沙异姓”。所谓“长沙王忠”，以致得到特殊优遇的原因，多有学者论述，然而似乎应当注意到，长沙王的特殊地位，很可能也与处于“南边”的背景有关。《汉书·高帝纪下》载封吴芮为长沙王的诏书中说，吴芮“从百粤之兵，以佐诸侯，诛暴秦，有大功”，“其以长沙、豫章、象郡、桂林、南海立番君芮为长沙王。”可知当时长沙国名义上的领地，竟然是包括南越地区的。
对于南越政权在秦末特殊的政治背景下生成的过程，司马迁在《史记·南越列传》中有这样的记述：赵佗，秦时任为南海郡龙川令。至秦二世时，南海郡尉任嚣病重将死，召见龙川令赵佗，对他说：听说陈胜等作乱，秦为无道，天下苦之，项羽、刘邦、陈胜、吴广等势力各自兴军聚众，虎争天下，中国扰乱，不知道什么时候才能安定，各地豪杰叛秦自立。南海地方僻远，我担心乱兵侵地危害这里，我准备兴兵断绝新道，自为防备，等待诸侯变乱的结局，然而已经病危。而番禺（今广东广州）地方有地理优势，便于防守，依恃南海，东西数千里，颇有中原人相辅，此亦一州之主也，可以立国。郡中长吏没有什么可以对话的，所以约你相谈。于是赵佗代为行使南海郡尉职能。任嚣去世，赵佗即移檄通告横浦关（今江西大余南）、阳山关（今广东阳山西北）、湟溪关（今广东英德西南），命令断绝道路，聚兵自守。秦王朝破灭之后，赵佗又击并桂林郡和象郡，自立为南越武王。
任嚣和赵佗，本人原先都是秦王朝委任的地方官，他们在秦末社会大动乱中的立场，一方面承认“秦为无道，天下苦之”，对于反抗秦政的斗争有所赞同，一方面则又“恐盗兵侵地至此”，于是“兴兵”而“自备”；一方面“以法诛秦所置长吏”，一方面则又“以其党为假守”。
从南海尉任嚣到南越武王赵佗，政治体制的基本形式和行政组织的基本构成，应当都是变化不大的。虽然我们不能具体地了解当时这样的政治结构在“负山险，阻南海，东西数千里”的南越地区，统治效能究竟能够达到什么程度，但是由所谓“颇有中国人相辅，此亦一州之主也，可以立国”的分析，可以知道这一政权从形式上来说，仍然是中原政治结构的翻版，尽管任嚣与赵佗间的权力转替的形式，隐约显现出原始时代军事民主制度影子。
据《史记·南越列传》记载，汉高祖初定天下，因为久经战乱，“中国劳苦”的缘故，当时以宽宏的态度容忍了赵佗政权在岭南的割据。又曾经派遣陆贾出使南越，承认了赵佗“南越王”的地位，希望他能够安定百越，并且保证“南边”的和平。
在高后专制的时代，“有司请禁南越关市铁器”，似乎曾经采取了与南越实行文化隔闭、文化封锁的政策。赵佗于是愤怒地说：高帝承认我南越的政治地位，通使节，交流物资，然而，“今高后听谗臣，别异蛮夷，隔绝器物”，这一定是长沙王的诡计，希望倚恃中原，击灭南越而兼并我们的土地，自为功也。赵佗“乃自尊号为南越武帝，发兵攻长沙边邑，败数县而去焉”。赵佗自立尊号，由“王”而“帝”，又北上发兵，似乎有所远图，但是进军规模适可而止，攻击对象也只是长沙王，表现出他的意图并不是真正要与汉王朝进行全面的武力对抗。
南越国与汉王朝正式进入交战状态，是吕后专政时代派周灶发军击南越以后的事。
对于周灶南征战事，司马迁在《史记·南越列传》中只有如下简单的记述：“高后遣将军隆虑侯灶往击之。会暑湿，士卒大疫，兵不能逾岭。岁余，高后崩，即罢兵。”因为气候条件的不适应，汉军不能逾岭，两军事实上在南岭一线相持了1年之久，吕后去世方才罢兵，于是出现了司马迁所谓“隆虑离湿疫，（赵）佗得以益骄”的局面。赵佗于是在实际上控制了闽越、西瓯、骆等部族，版图至于东西万余里，又乘坐皇家车辆，采用皇家制度，要与汉王朝分庭抗礼。
汉文帝即位，对于吕后时代政治多所否定，为赵佗照料在真定（今河北石家庄东北）的家族墓园，派专职官吏管理，每年定时祭祀。对于赵佗的亲属，也都给予高官厚赐。
据《汉书·南粤传》，汉文帝又派陆贾为使者出使南越，赐书致意，文辞颇为诚挚：“皇帝谨问南粤王，甚苦心劳意。朕，高皇帝侧室之子，弃外奉北藩于代，道里辽远，壅蔽朴愚，未尝致书。”汉文帝又写道：朕以王侯百官不释之故，不得不立，现今即位。得知王曾经致书将军隆虑侯书，寻求亲族兄弟，请罢长沙两将军。朕按照王的要求已经罢将军博阳侯，亲族兄弟在真定者，已派人存问，王先人的冢墓，也已经修治。前日听说王发兵于边，为寇灾不止。长沙国和南郡都受到危害。难道王的国度，竟然会只得到利益吗？两军交战，必多杀士卒，伤良将吏，寡人之妻，孤人之子，独人父母，所得一而所失十，朕不忍为也。朕准备调整边界，而主管官员说，这是高皇帝所确定的，因而朕不得擅变焉。王之号为帝，两帝并立，没有一乘之使以通其道，必然导致争。争而不让，仁者不为也。朕愿意与王分弃前患，终今以来，通使如故。因而派陆贾驰谕告王朕意，希望王亦受之，不要再用战争导致民众的灾害。上褚五十衣，中褚三十衣，下褚二十衣，作为礼品送给王。愿王听乐娱忧，存问邻国。
这是一篇情感诚恳，言辞亲和，足以打动人心的外交文书。
果然，据《史记·南越列传》，陆贾至南越，南越王十分恐惧，致书请罪。其中写道：蛮夷大长老夫臣佗，前日高后隔异南越，窃疑长沙王谗臣，又遥闻高后尽诛佗宗族，掘烧先人冢，以故自弃，犯长沙边境。且南方卑湿，蛮夷中间，其东闽越千人众号称王，其西瓯越裸国亦称王。老臣妄窃帝号，聊以自娱，怎么敢向皇帝提什么要求呢？于是叩头请罪，表示愿意长为藩臣，奉贡职。于是乃下令国中：自今以后，废去帝制。
《汉书·南粤传》的记载则更为详细，其大意略同。赵佗致书，解释了当时称帝之原委，他说道：“蛮夷大长老夫臣佗昧死再拜上书皇帝陛下：老夫故粤吏也，高皇帝幸赐臣佗玺，以为南粤王，使为外臣，时内贡职。孝惠皇帝即位，义不忍绝，所以赐老夫者甚厚。高后自临用事，近细士，信谗臣，别异蛮夷，出令曰：‘毋予蛮夷外粤金铁田器，马牛羊即予，予牡，毋予牝。’”老夫身处僻远之地，年岁已长，自以祭祀不修，有死罪，相继使内臣藩、中尉高、御史平凡三个使团上书谢过，然而都没有返回。又风闻老夫父母坟墓已坏削，兄弟宗族已诛论。下属官吏相聚商议，于是更号为“帝”，不过是“自帝其国”，绝不敢有害于天下啊。高皇后闻之大怒，削去南粤之籍，使使不通。老夫窃疑长沙王谗臣，故敢发兵以伐其边。且南方卑湿，蛮夷中西有西瓯，其众半羸，南面称王；东有闽粤，其众数千人，亦称王；西北有长沙，其半蛮夷，亦称王。老夫所以敢于妄窃帝号，聊以自娱。老夫身定百邑之地，东西南北数千万里，带甲百万有余，然北面而臣事汉，这是为什么呢？不敢背先人之故。老夫处粤四十九年，于今已经抱孙子啦。然而夙兴夜寐，寝不安席，食不甘味，目不视靡曼之色，耳不听钟鼓之音者，正是因为不得服务于汉啊。今陛下幸哀怜，复故号，通使汉如故，老夫死骨不腐，改号不敢为帝矣！“谨北面因使者献白璧一双，翠鸟千，犀角十，紫贝五百，桂蠹一器，生翠四十双，孔雀二双。”
赵佗致汉文帝书同样情感诚恳，言辞亲和，足以打动人心。
据说“陆贾还报，文帝大说”。于是，一直到汉景帝时代，南越“称臣遣使入朝请”。不过，暗自仍然沿用旧的称号，“然南越其居国窃如故号名，其使天子，称王朝命如诸侯。”
