Following the collapse of the Qin dynasty, Zhao Tuo took control of Guangzhou and extended his territory south of the Red River as one of the primary targets of the Qin dynasty was to secure important coastal seaports for trade.^[34] The First Emperor died in 210 BCE, and his son Zhao Huhai became the Second Emperor of Qin. In 206 BCE the Qin dynasty ceased to exist, and the Yue peoples of Guilin and Xiang were largely independent once more. In 204 BCE, Zhao Tuo founded the Kingdom of Nanyue, with Panyu as capital, and declared himself the Martial King of Nanyue and divided his empire into seven provinces, which were administered by a mix of Han Chinese and Yue feudal lords.^[35]

Liu Bang, after years of war with his rivals, established the Han dynasty and reunified Central China in 202 BCE. In 196 BCE, Liu Bang, now Emperor Gaozu, sent Lu Jia to Nanyue in hopes of obtaining Zhao Tuo's allegiance. After arriving, Lu met with Zhao Tuo and is said to have found him dressed in Yue clothing and being greeted after their customs, which enraged him. A long exchange ensued,^[36] wherein Lu is said to have admonished Zhao Tuo, pointing out that he was Chinese, not Yue, and should have maintained the dress and decorum of the Chinese and not have forgotten the traditions of his ancestors. Lu lauded the strength of the Han court and warned against a kingdom as small as Nanyue daring to oppose it. He further threatened to kill Zhao's kinsmen in China proper and destroying their ancestral graveyards, as well as coercing the Yue into deposing Zhao himself. Following the threat, Zhao Tuo then decided to receive Emperor Gaozu's seal and submit to Han authority. Trade relations were established at the border between Nanyue and the Han kingdom of Changsha. Although formally a Han subject state, Nanyue seems to have retained a large measure of de facto autonomy.

The kingdom of Âu Lạc laid south of Nanyue in the early years of Nanyue's existence, with Âu Lạc located primarily in the Red River delta area, and Nanyue encompassing Nanhai, Guilin, and Xiang Commanderies. During the time when Nanyue and Âu Lạc co-existed, Âu Lạc acknowledged Nanyue's suzerainty, especially because of their mutual anti-Han sentiment. Zhao Tuo built up and reinforced his army, fearing an attack by the Han. However, when relations between the Han and Nanyue improved, in 179 BCE, Zhao Tuo defeated King An Dương Vương and annexed Âu Lạc.^[37]