This research focuses on the emergence and formation of Linyi, one of the earliest polities in Nanhai, namely, Southeast Asia. The Japanese-Vietnamese collaborative project has been carried out at the Tra Kieu site in central Vietnam, which has been identified as an old capital of Linyi. Two seasons’ excavations on the eastern rampart of Tra Kieu were conducted by the project team, with the intention of verifying the date and structure. As a result of this work, two rows of brick walls were unearthed with infill clay layers between them, regarded as the main structure of initial rampart dating from the latter half of the third century to the fourth century CE. This structure was subsequently enlarged at least twice, and these works probably ranged from the fourth to the beginning of the sixth century CE. These results of excavations have brought new perspectives on historical study of Linyi, and other ancient polities in Southeast Asia.