This article argues that the end of the Cold War can be told as a story of the development of trust. Despite its centrality as a political concept, trust has only recently received focused attention in the field of international relations. Development of trust cannot be reduced to changing relationships of power or redefinitions of interests but requires communicative elements. The argument is demonstrated through a comparison of German–Soviet and Japanese–Soviet relations at the end of the Cold War. The key point is that trust and the lack of it, respectively, were a major factor in the profound transformation of the former relationship and led to stalemate in the latter.