World trade relationships are changing rapidly. Regional trade arrangements proliferate even with considerable progress in multilateral trade liberalization. Without any institutional framework on regional integration, however, the three Northeast Asian countries, i.e., China, Japan and Korea, have been experiencing significant changes and progress in their economic relationships in trade, especially during the last two decades or so. The purpose of this paper is to examine the trade structure of the three Northeast Asian countries, especially, in terms of complementarity through the index of trade conformity (ITC) and to estimate trade potential with the gravity model of trade considering the directions of trade between them. The three Northeast Asian countries are analyzed as having relatively high complementarity in their trade structure, especially in trade flows from Korea to both China and Japan followed by those from Japan to China. Potential trades between them are also estimated significantly larger than their actual trade performances. Based on the results, some measures to attain the potential trades are suggested, for example, implementing trade facilitation measures, utilizing complementarity in trade between them, and introducing institutional integrations such as a regional trade arrangement.