Setelah runtuhnya dinasti Qin , Zhao Tuo menguasai Guangzhou dan memperluas wilayahnya ke selatan Sungai Merah karena salah satu target utama dinasti Qin adalah mengamankan pelabuhan pesisir penting untuk perdagangan.^[34] Kaisar Pertama meninggal pada tahun 210 SM, dan putranya Zhao Huhai menjadi Kaisar Kedua Qin.Pada tahun 206 SM, Dinasti Qin tidak ada lagi, dan suku Yue di Guilin dan Xiang kembali merdeka.Pada tahun 204 SM, Zhao Tuo mendirikan Kerajaan Nanyue, dengan Panyu sebagai ibu kotanya, dan mendeklarasikan dirinya sebagai Raja Bela Diri Nanyue dan membagi kerajaannya menjadi tujuh provinsi, yang dikelola oleh campuran penguasa feodal Tiongkok Han dan Yue.^[35]Liu Bang, setelah bertahun-tahun berperang dengan saingannya, mendirikan Dinasti Han dan menyatukan kembali Tiongkok Tengah pada tahun 202 SM.Pada tahun 196 SM, Liu Bang, yang sekarang menjadi Kaisar Gaozu, mengirim Lu Jia ke Nanyue dengan harapan mendapatkan kesetiaan Zhao Tuo.Setelah tiba, Lu bertemu dengan Zhao Tuo dan dikatakan menemukannya mengenakan pakaian Yue dan disambut sesuai adat istiadat mereka, yang membuatnya marah.Pertengkaran panjang pun terjadi, ^[36] dimana Lu dikatakan telah menegur Zhao Tuo, dengan menunjukkan bahwa dia adalah orang Tionghoa, bukan Yue, dan seharusnya menjaga pakaian dan kesopanan orang Tionghoa dan tidak melupakan tradisi leluhurnya.Lu memuji kekuatan istana Han dan memperingatkan kerajaan sekecil Nanyue yang berani menentangnya.Dia selanjutnya mengancam akan membunuh sanak saudara Zhao di Tiongkok dan menghancurkan kuburan leluhur mereka, serta memaksa Yue untuk menggulingkan Zhao sendiri.Menyusul ancaman tersebut, Zhao Tuo kemudian memutuskan untuk menerima segel Kaisar Gaozu dan tunduk pada otoritas Han.Hubungan perdagangan terjalin di perbatasan antara Nanyue dan kerajaan Han di Changsha.Meskipun secara resmi merupakan negara bagian Han, Nanyue tampaknya masih memiliki otonomi de facto yang besar.Kerajaan Âu Lạc terletak di selatan Nanyue pada tahun-tahun awal keberadaan Nanyue, dengan Âu Lạc terletak terutama di kawasan delta Sungai Merah, dan Nanyue meliputi Komando Nanhai, Guilin, dan Xiang.Pada saat Nanyue dan Âu Lạc hidup berdampingan, Âu Lạc mengakui kekuasaan Nanyue, terutama karena sentimen anti-Han mereka.Zhao Tuo membangun dan memperkuat pasukannya, karena takut akan serangan Han.Namun, ketika hubungan antara Han dan Nanyue membaik, pada tahun 179 SM, Zhao Tuo mengalahkan Raja An Dương Vương dan mencaplok Âu Lạc.^[37]