Po zhroucení dynastie Qin převzal Zhao Tuo kontrolu nad Guangzhou a rozšířil své území jižně od Rudé řeky, protože jedním z primárních cílů dynastie Qin bylo zajistit důležité pobřežní přístavy pro obchod.^[34] První císař zemřel v roce 210 př. n. l. a jeho syn Zhao Huhai se stal druhým císařem Qin.V roce 206 př. n. l. dynastie Qin přestala existovat a národy Yue z Guilin a Xiang byly opět z velké části nezávislé.V roce 204 př. n. l. založil Zhao Tuo království Nanyue s Panyu jako hlavním městem a prohlásil se válečným králem Nanyue a rozdělil svou říši na sedm provincií, které spravovala směs feudálních pánů Han Číňanů a Yue.^[35]Liu Bang po letech války se svými rivaly založil dynastii Han a znovu sjednotil střední Čínu v roce 202 př.V roce 196 př. n. l. poslal Liu Bang, nyní císař Gaozu, Lu Ťia do Nanyue v naději, že získá věrnost Zhao Tuo.Po příjezdu se Lu setkal se Zhao Tuo a říká se, že ho našel oblečeného v oblečení Yue a vítali ho podle jejich zvyků, což ho rozzuřilo.Následovala dlouhá výměna názorů ^[36] , kde Lu údajně napomínal Zhao Tuo a poukazoval na to, že byl Číňan, ne Yue, a měl si zachovat oděv a dekorum Číňanů a nezapomínat na tradice svých předků.Lu chválil sílu hanského dvora a varoval před královstvím tak malým jako Nanyue, které by se mu odvážilo postavit.Dále vyhrožoval, že zabije Zhaovy příbuzné ve vlastní Číně a zničí hřbitovy jejich předků, stejně jako donutí Yue, aby sesadil samotného Zhaa.Po hrozbě se Zhao Tuo rozhodl přijmout pečeť císaře Gaozu a podřídit se autoritě Han.Obchodní vztahy byly navázány na hranici mezi Nanyue a Hanským královstvím Changsha.Přestože je Nanyue formálně podřízeným státem Han, zdá se, že si zachoval velkou míru de facto autonomie.Království Âu Lạc leželo jižně od Nanyue v prvních letech existence Nanyue, přičemž Âu Lạc se nacházelo především v oblasti delty Red River a Nanyue zahrnovalo Nanhai, Guilin a Xiang Commanderies.Během doby, kdy Nanyue a Âu Lạc koexistovali, Âu Lạc uznal Nanyueovu suverenitu, zejména kvůli jejich vzájemnému protihanskému sentimentu.Zhao Tuo vybudoval a posílil svou armádu, protože se bál útoku Hanů.Když se však vztahy mezi Hanem a Nanyue zlepšily, v roce 179 př. n. l. Zhao Tuo porazil krále An Dương Vương a anektoval Âu Lạc.^[37]