Etter sammenbruddet av Qin-dynastiet tok Zhao Tuo kontroll over Guangzhou og utvidet sitt territorium sør for Red River, da et av Qin-dynastiets primære mål var å sikre viktige kysthavner for handel.^[34] Den første keiseren døde i 210 fvt, og hans sønn Zhao Huhai ble den andre keiseren av Qin.I 206 fvt sluttet Qin-dynastiet å eksistere, og Yue-folkene i Guilin og Xiang var i stor grad uavhengige igjen.I 204 fvt grunnla Zhao Tuo kongeriket Nanyue, med Panyu som hovedstad, og erklærte seg selv som krigskongen av Nanyue og delte imperiet hans inn i syv provinser, som ble administrert av en blanding av Han-kinesere og Yue-føydalherrer.^[35]Liu Bang, etter år med krig med sine rivaler, etablerte Han-dynastiet og gjenforent Sentral-Kina i 202 fvt.I 196 fvt sendte Liu Bang, nå keiser Gaozu, Lu Jia til Nanyue i håp om å oppnå Zhao Tuos troskap.Etter å ha ankommet, møtte Lu Zhao Tuo og sies å ha funnet ham kledd i Yue-klær og blitt møtt etter deres skikker, noe som gjorde ham rasende.En lang utveksling fulgte, ^[36] der Lu sies å ha formanet Zhao Tuo, og påpekte at han var kineser, ikke Yue, og burde ha opprettholdt kinesernes kjole og dekor og ikke ha glemt tradisjonene til sine forfedre.Lu roste styrken til Han-domstolen og advarte mot at et kongerike så lite som Nanyue våget å motsette seg det.Han truet videre med å drepe Zhaos slektninger i Kina og ødelegge deres forfedres kirkegårder, i tillegg til å tvinge Yue til å avsette Zhao selv.Etter trusselen bestemte Zhao Tuo seg for å motta keiser Gaozus segl og underkaste seg Han-myndighet.Handelsforbindelser ble etablert ved grensen mellom Nanyue og Han-riket Changsha.Selv om det formelt er en Han-subjektstat, ser det ut til at Nanyue har beholdt et stort mål av de facto autonomi.Kongedømmet Âu Lạc lå sør for Nanyue i de første årene av Nanyues eksistens, med Âu Lạc som hovedsakelig ligger i Red River-deltaområdet, og Nanyue som omfatter Nanhai, Guilin og Xiang Commanderies.I løpet av tiden da Nanyue og Âu Lạc eksisterte sammen, erkjente Âu Lạc Nanyues suverenitet, spesielt på grunn av deres gjensidige anti-Han-følelse.Zhao Tuo bygget opp og forsterket hæren sin, i frykt for et angrep fra Han.Men da forholdet mellom Han og Nanyue ble bedre, i 179 fvt, beseiret Zhao Tuo kong An Dương Vương og annekterte Âu Lạc.^[37]