Adopting the historical periodization and the “ethnic awakening” theory of Konan Naito, this essay discusses the early formation of East Asian states such as Koguryō, Paekche, Silla and Wa during the 4th and 5th centuries, as well as the political order within the East Asian society shaped by the enfeoffment of the Eastern Jin and the Southern dynasties by using Chinese sources. It argues that the cultural influences of the Qin and Han dynasties promoted the ethnic awakening of East Asian peoples, and during the turmoil periods of the Wei, the Jin, and the Division Era these ethnic groups leaped rapidly in their roads of state-formation. The enfeoffment system of the Eastern Jin played significant role in this process, and therefore set up the basic structure of the international relationship in early modern East Asia.