This area was also the place for the kingdom of Minyue perhaps an ethnic name and associated with the Chinese word for barbarians, and "Yue", after the State of Yue, a Spring and Autumn Period kingdom in Zhejiang Province to the north. This is because the royal family of Yue fled to Fujian after their kingdom was annexed by the State of Chu in 306 BC. Min is also the name of the main river in this area, but the ethnonym is probably earlier.

Minyue was a de facto kingdom until the emperor of Qin Dynasty, the first unified imperial Chinese state, abolished the status. In the aftermath of the fall of the Qin Dynasty, however, civil war broke out between two warlords, Xiang Yu and Liu Bang; the Minyue king Wuzhu sent his troops to fight side-by-side with Liu Bang, and his gamble paid off. Liu Bang was victorious, and founded the Han Dynasty; in 202 BC he restored Minyue's status as a tributary independent kingdom.