The processes of making foreign policy decisions and forming assumptions about the nature of the “other” comprise major challenges to the transformation of conflictual relationships and construction of an enduring peace in Northeast Asia. In this article, in order to make progress towards these goals, methodologies for unpacking the “black box of decision,” understanding the “other,” deconstructing the relationship between positions and interests, and increasing the role played by non-state and substate actors are explored. The paper first assesses theoretical and practical tools used for addressing the problems. It then considers other conflictual relationships that have faced similar obstacles, and the processes which were employed in an attempt to ameliorate them. It concludes with a policy prescription for breaking the vicious cycle of hurt, blame, and rising nationalism in the region.