A Qin-dinasztia összeomlását követően Zhao Tuo átvette az irányítást Kanton felett, és kiterjesztette területét a Vörös-folyótól délre, mivel a Qin-dinasztia egyik elsődleges célja az volt, hogy fontos tengerparti tengeri kikötőket biztosítson a kereskedelem számára.^[34] Az első császár ie 210-ben halt meg, fia, Zhao Huhai pedig Qin második császára lett.I.e. 206-ban a Qin-dinasztia megszűnt, és Guilin és Xiang Yue népei ismét nagyrészt függetlenek lettek.I. e. 204-ben Zhao Tuo megalapította Nanyue Királyságot, Panyu fővárosával, és Nanyue harci királyának nyilvánította magát, birodalmát pedig hét tartományra osztotta, amelyeket a Han kínai és a Yue feudális urak keveréke igazgat.^[35]Liu Bang a riválisaival vívott évek háborúja után megalapította a Han-dinasztiát , és ie 202-ben újraegyesítette Közép-Kínát.I. e. 196-ban Liu Bang, ma Gaozu császár elküldte Lu Jiát Nanyuébe, annak reményében, hogy megszerezze Zhao Tuo hűségét.Érkezése után Lu találkozott Zhao Tuo-val, és állítólag Yue ruhába öltözve találta, és a szokásaik szerint fogadták, ami feldühítette.Hosszú eszmecsere következett, ^[36] amelyben Lu állítólag intette Zhao Tuot, rámutatva arra, hogy ő kínai, nem Yue, és meg kellett volna őriznie a kínaiak öltözködését és dekorációját, és nem feledkezett meg ősei hagyományairól.Lu méltatta a Han udvar erejét, és óva intett attól, hogy egy olyan kicsi királyság, mint Nanyue, szembe merjen állni vele.Továbbá azzal fenyegetőzött, hogy megöli Zhao rokonait Kínában, és elpusztítja őseik temetőit, valamint arra kényszeríti a Yue-t, hogy magát Zhaot leváltsák.A fenyegetést követően Zhao Tuo úgy döntött, hogy megkapja Gaozu császár pecsétjét, és aláveti magát Han tekintélyének.A kereskedelmi kapcsolatok Nanyue és Changsha Han királysága határán jöttek létre.Noha formálisan Han alattvaló állam, úgy tűnik, hogy Nanyue nagymértékben megőrizte de facto autonómiáját.Âu Lạc királysága Nanyue-tól délre feküdt Nanyue fennállásának korai éveiben, Âu Lạc elsősorban a Vörös-folyó delta területén, Nanyue pedig Nanhai, Guilin és Xiang Commanderies-t foglalja magában.Abban az időben, amikor Nanyue és Âu Lạc együtt léteztek, Âu Lạc elismerte Nanyue szuzerenitását, különösen a kölcsönös Han-ellenességük miatt.Zhao Tuo felépítette és megerősítette seregét, tartva a hanok támadásától.Amikor azonban a Han és Nanyue közötti kapcsolatok javultak, ie 179-ben Zhao Tuo legyőzte An Dương Vương királyt és annektálta Âu Lạc-et.^[37]