The purpose of this paper is to historically analyze the developmental aspect of the Korea-Japan relationship within the structural change of the Cold War system in East Asia at the end of the 1960's. Specifically, it focuses on the case of Okinawa reversion and the U. S. troop withdrawal from Korea.Following are the important findings: first, the 'Korea clause' was not only the product of compromise between the interests of U. S. and Japan, but also the results from Korea's claim that the Okinawa issue is directly related to the regional security in Asia; second, it shows the dilemma of small nations' diplomacy in that, the Korean government utilized the Japanese support to prevent U. S. government's plan to withdraw its troops from Korea, while at the same time Korea was concerned about the situation where the Korean peninsula issue would be decided by great powers regardless of Korea's intention; third, by dividing the Korea-Japan relationship into three period of mutual hostility, mutual convergence of security perception and mutual conflict, we find the dynamic changes of security perception gap between two countries within international environment.