Why do multiple understandings of state sovereignty exist in East Asia, and how do they affect security outcomes at the regional and domestic levels? I argue that Japanese and Korean leaders have historically sought to generate political legitimacy through alternative state-strengthening strategies, integration or insulation, vis-a-vis the region's dominant power in the context of regional hierarchy. These varying ideas on achieving greater international status have remained an integral part of domestic security debates in Japan and Korea, which I refer to in this study as the framework of sovereign-nationalism. Through comparative case studies, I show evidence of varying but enduring patterns of hierarchical interaction and domestic legitimacy politics by examining Japanese and Korean security relations with China in the traditional East Asian order and with the United States in the post-1945 regional alliance system. In addition, I identify the mechanisms through which these ideas and practices of statestrengthening are reproduced and translated into political outcomes: framing through issue linkages and rhetorical entrapment.