Nakon sloma dinastije Qin , Zhao Tuo je preuzeo kontrolu nad Guangzhouom i proširio svoj teritorij južno od Crvene rijeke jer je jedan od primarnih ciljeva dinastije Qin bio osigurati važne obalne luke za trgovinu.^[34] Prvi car je umro 210. godine prije Krista, a njegov sin Zhao Huhai postao je Drugi car Qina.Godine 206. pr. Kr. dinastija Qin prestala je postojati, a narodi Yue Guilin i Xiang ponovno su bili uglavnom neovisni.Godine 204. pr. Kr., Zhao Tuo je osnovao Kraljevstvo Nanyue, s Panyuom kao glavnim gradom, proglasio se ratnim kraljem Nanyuea i podijelio svoje carstvo na sedam provincija, kojima je upravljala mješavina feudalnih gospodara Han Kineza i Yuea.^[35]Liu Bang, nakon godina rata sa svojim suparnicima, uspostavio je dinastiju Han i ponovno ujedinio središnju Kinu 202. godine pr.Godine 196. pr. Kr., Liu Bang, sada car Gaozu, poslao je Lu Jia u Nanyue u nadi da će pridobiti odanost Zhao Tuoa.Nakon što je stigao, Lu se sastao sa Zhao Tuom i navodno ga je zatekao odjevenog u Yue odjeću i kako ga pozdravljaju po njihovim običajima, što ga je razbjesnilo.Uslijedila je duga razmjena ^[36] u kojoj je Lu rekao da je opomenuo Zhao Tuoa, ističući da je on Kinez, a ne Yue, i da je trebao zadržati odjeću i pristojnost Kineza i da nije zaboravio tradiciju svojih predaka.Lu je hvalio snagu Hanskog dvora i upozoravao da mu se tako malo kraljevstvo poput Nanyue ne usuđuje suprotstaviti.Nadalje je prijetio da će ubiti Zhaove rođake u Kini i uništiti groblja njihovih predaka, kao i da će prisiliti Yue da svrgne samog Zhaoa.Nakon prijetnje, Zhao Tuo je tada odlučio primiti pečat cara Gaozua i pokoriti se Hanskoj vlasti.Trgovački odnosi uspostavljeni su na granici između Nanyue i Han kraljevstva Changsha.Iako je formalno podređena država Han, čini se da je Nanyue zadržao veliku mjeru de facto autonomije.Kraljevstvo Âu Lạc nalazilo se južno od Nanyuea u ranim godinama postojanja Nanyuea, s Âu Lạc smještenim prvenstveno u području delte Crvene rijeke, a Nanyue je obuhvaćao Nanhai, Guilin i Xiang Commanderies.Tijekom vremena kada su Nanyue i Âu Lạc koegzistirali, Âu Lạc je priznao Nanyueinu vrhovnu vlast, posebno zbog njihovog zajedničkog anti-Han osjećaja.Zhao Tuo je izgradio i pojačao svoju vojsku, bojeći se napada Hana.Međutim, kada su se odnosi između Hana i Nanyuea popravili, 179. godine prije Krista, Zhao Tuo je porazio kralja An Dương Vươnga i pripojio Âu Lạc.^[37]