Po upadku dynastii Qin Zhao Tuo przejął kontrolę nad Kantonem i rozszerzył swoje terytorium na południe od Rzeki Czerwonej, ponieważ jednym z głównych celów dynastii Qin było zabezpieczenie ważnych przybrzeżnych portów morskich dla handlu.^[34] Pierwszy Cesarz zmarł w 210 roku p.n.e., a jego syn Zhao Huhai został Drugim Cesarzem Qin.W 206 roku p.n.e. dynastia Qin przestała istnieć, a ludy Yue z Guilin i Xiang ponownie uzyskały w dużej mierze niepodległość.W 204 roku p.n.e. Zhao Tuo założył Królestwo Nanyue ze stolicą w Panyu, ogłosił się Królem Wojennym Nanyue i podzielił swoje imperium na siedem prowincji, którymi zarządzali Chińczycy Han i feudalni panowie Yue.^[35]Liu Bang po latach wojny ze swoimi rywalami założył dynastię Han i ponownie zjednoczył środkowe Chiny w 202 roku p.n.e.W 196 roku p.n.e. Liu Bang, obecnie cesarz Gaozu, wysłał Lu Jia do Nanyue w nadziei, że uzyska lojalność Zhao Tuo.Po przybyciu na miejsce Lu spotkał się z Zhao Tuo i podobno zastał go ubranego w strój Yue i witanego zgodnie z ich zwyczajami, co go rozwścieczyło.Nastąpiła długa wymiana zdań, podczas której Lu ^[podobno] upomniał Zhao Tuo, wskazując, że to on jest Chińczykiem, a nie Yue, i powinien był zachować ubiór i przyzwoitość Chińczyków oraz nie zapomnieć tradycji swoich przodków.Lu wychwalał siłę dworu Han i ostrzegał przed tak małym królestwem jak Nanyue, które ośmieliło się mu przeciwstawić.Następnie zagroził, że zabije krewnych Zhao we właściwych Chinach i zniszczy cmentarze ich przodków, a także zmusił Yue do obalenia samego Zhao.W odpowiedzi na groźbę Zhao Tuo zdecydował się przyjąć pieczęć cesarza Gaozu i poddać się władzy Han.Nawiązano stosunki handlowe na granicy Nanyue i królestwa Han Changsha.Wydaje się, że choć formalnie należało do państwa Han, Nanyue zachowało znaczną część de facto autonomii.Królestwo Âu Lạc leżało na południe od Nanyue we wczesnych latach istnienia Nanyue, z Âu Lạc położonym głównie w obszarze delty Rzeki Czerwonej, a Nanyue obejmującym dowództwa Nanhai, Guilin i Xiang.W czasie, gdy Nanyue i Âu Lạc współistniały, Âu Lạc uznał zwierzchnictwo Nanyue, zwłaszcza ze względu na ich wzajemne nastroje anty-Han.Zhao Tuo zbudował i wzmocnił swoją armię w obawie przed atakiem Han.Jednak gdy stosunki między Hanem i Nanyue poprawiły się, w 179 roku p.n.e. Zhao Tuo pokonał króla An Dương Vương i zaanektował Âu Lạc.^[37]