Após o colapso da dinastia Qin , Zhao Tuo assumiu o controle de Guangzhou e estendeu seu território ao sul do Rio Vermelho, já que um dos principais alvos da dinastia Qin era garantir importantes portos marítimos costeiros para o comércio.^[34] O Primeiro Imperador morreu em 210 aC, e seu filho Zhao Huhai tornou-se o Segundo Imperador de Qin.Em 206 aC, a dinastia Qin deixou de existir e os povos Yue de Guilin e Xiang tornaram-se em grande parte independentes mais uma vez.Em 204 aC, Zhao Tuo fundou o Reino de Nanyue, com Panyu como capital, e declarou-se o Rei Marcial de Nanyue e dividiu seu império em sete províncias, que eram administradas por uma mistura de senhores feudais chineses Han e Yue.^[35]Liu Bang, após anos de guerra com seus rivais, estabeleceu a dinastia Han e reunificou a China Central em 202 aC.Em 196 aC, Liu Bang, agora imperador Gaozu, enviou Lu Jia a Nanyue na esperança de obter a lealdade de Zhao Tuo.Depois de chegar, Lu se encontrou com Zhao Tuo e disse tê-lo encontrado vestido com roupas de Yue e sendo saudado de acordo com seus costumes, o que o enfureceu.Seguiu-se uma longa conversa, ^[36] na qual Lu teria advertido Zhao Tuo, apontando que ele era chinês, não Yue, e deveria ter mantido a vestimenta e o decoro dos chineses e não ter esquecido as tradições de seus ancestrais.Lu elogiou a força da corte Han e alertou contra um reino tão pequeno como Nanyue que ousasse se opor a ela.Ele ainda ameaçou matar os parentes de Zhao na própria China e destruir seus cemitérios ancestrais, bem como coagir os Yue a depor o próprio Zhao.Após a ameaça, Zhao Tuo decidiu receber o selo do Imperador Gaozu e submeter-se à autoridade Han.As relações comerciais foram estabelecidas na fronteira entre Nanyue e o reino Han de Changsha.Embora formalmente um estado súdito Han, Nanyue parece ter mantido uma grande medida de autonomia de facto.O reino de Âu Lạc ficava ao sul de Nanyue nos primeiros anos de existência de Nanyue, com Âu Lạc localizado principalmente na área do delta do Rio Vermelho, e Nanyue abrangendo as Comendas de Nanhai, Guilin e Xiang.Durante o tempo em que Nanyue e Âu Lạc coexistiram, Âu Lạc reconheceu a suserania de Nanyue, especialmente por causa de seu sentimento mútuo anti-Han.Zhao Tuo construiu e reforçou seu exército, temendo um ataque dos Han.No entanto, quando as relações entre Han e Nanyue melhoraram, em 179 aC, Zhao Tuo derrotou o rei An Dương Vương e anexou Âu Lạc.^[37]