Na de ineenstorting van de Qin-dynastie nam Zhao Tuo de controle over Guangzhou over en breidde zijn grondgebied ten zuiden van de Rode Rivier uit, aangezien een van de belangrijkste doelen van de Qin-dynastie het veiligstellen van belangrijke zeehavens aan de kust was voor handel.^[34] De eerste keizer stierf in 210 vGT, en zijn zoon Zhao Huhai werd de tweede keizer van Qin.In 206 vGT hield de Qin-dynastie op te bestaan ​​en waren de Yue-volkeren Guilin en Xiang weer grotendeels onafhankelijk.In 204 vGT stichtte Zhao Tuo het koninkrijk Nanyue, met Panyu als hoofdstad, en riep zichzelf uit tot krijgskoning van Nanyue en verdeelde zijn rijk in zeven provincies, die werden bestuurd door een mix van Han-Chinezen en Yue-feodale heren.^[35]Liu Bang stichtte, na jaren van oorlog met zijn rivalen, de Han-dynastie en herenigde Centraal-China in 202 vGT.In 196 vGT stuurde Liu Bang, nu keizer Gaozu, Lu Jia naar Nanyue in de hoop de trouw van Zhao Tuo te verkrijgen.Na aankomst ontmoette Lu Zhao Tuo en er wordt gezegd dat hij hem gekleed in Yue-kleding had aangetroffen en werd begroet na hun gebruiken, wat hem woedend maakte.Er volgde een lange woordenwisseling, ^[36] waarin Lu Zhao Tuo zou hebben vermaand, erop wijzend dat hij Chinees was, en niet Yue, en de kleding en het decorum van de Chinezen had moeten behouden en de tradities van zijn voorouders niet had moeten vergeten.Lu prees de kracht van het Han-hof en waarschuwde ervoor dat een koninkrijk zo klein als Nanyue zich ertegen zou verzetten.Hij dreigde verder Zhao's verwanten in China te vermoorden en hun voorouderlijke begraafplaatsen te vernietigen, en hij dwong de Yue om Zhao zelf af te zetten.Na de dreiging besloot Zhao Tuo vervolgens het zegel van keizer Gaozu te ontvangen en zich te onderwerpen aan het gezag van Han.Handelsbetrekkingen werden tot stand gebracht aan de grens tussen Nanyue en het Han-koninkrijk Changsha.Hoewel Nanyue formeel een Han-onderdaan was, lijkt het erop dat ze een grote mate van de facto autonomie heeft behouden.Het koninkrijk Âu Lạc lag ten zuiden van Nanyue in de eerste jaren van Nanyue's bestaan, waarbij Âu Lạc voornamelijk in het deltagebied van de Rode Rivier lag, en Nanyue de Commanderies Nanhai, Guilin en Xiang omvatte.Gedurende de tijd dat Nanyue en Âu Lạc naast elkaar bestonden, erkende Âu Lạc de heerschappij van Nanyue, vooral vanwege hun wederzijdse anti-Han-sentiment.Zhao Tuo bouwde en versterkte zijn leger, uit angst voor een aanval van de Han.Toen de betrekkingen tussen de Han en Nanyue echter verbeterden, versloeg Zhao Tuo in 179 vGT koning An Dương Vương en annexeerde Âu Lạc.^[37]