Japan and South Korea formed an alliance with the United States against the communist bloc during the Cold War era and have maintained the alliance after the end of the Cold War to deter and contain a threat from North Korea’s nuclear and missile development. Since the democratization of South Korea in the late 1980s, the democratic political regime of South Korea has resembled that of Japan, yet the two countries still suffer from discord over historical problems such as the “comfort women” issue, textbook controversies, the Yasukuni Shrine problem, and so forth. With reference to alliance dilemma, which refers to a fear of entrapment or abandonment, and the discrepancy in their approaches to historical issues and transitional justice, this paper aims to explain why discord between Japan and South Korea continues in spite of the similarity of their political structures and a shared security alliance.