The paper attempts to approach the survival of the North Korean regime in the perspective of changing legitimation modes and ideological management by the leadership to fill in possible 'identity vacuum'. With a content analysis of Rodong Sinmun, the representative North Korean newspaper, this paper follows the reformulation process of the legitimising value and ideological rationality in North Korea between 1980 and 2004. It particularly looks at changes in the Party discourse, political rhetoric, and the emphasis of the Party policy focus during the analytical period in order to trace the leadership's effort to provide new goals, vision, and regime legitimacy as a way to overcome crises. On the basis of findings, the paper argues that the North Korean regime formulated new rhetoric at different times to rationalise its existence, which consequently transformed the nature of the regime from a 'Juche (self-reliant)’ state to a 'military oriented' one where the 'Songun (military first)' ideology established itself as a dominating rhetoric. In the perspective of legitimation crisis, the paper further argues that the process of shifting legitimation modes, through ideological manipulation or propaganda management has served the purpose of preventing identity crisis and sustaining the North Korean regime thus far.