The end of the Cold War led to intense debates about how change happens in international politics. In this article, we argue that practice theory has great potential for illuminating this question. Drawing on Vincent Pouliot’s empirical analysis of NATO-Russia relations after the end of the Cold War, we elaborate how change happens in and through practice. We show that post-Cold War security practices are inherently unstable, because there is a fundamental uncertainty about whether the Cold War is really over or whether the Cold War logic of bipolar confrontation still applies. Uncertainty about the meaning of the past destabilizes present practices and thus makes sudden and drastic change possible. To date, many contributions to the literature on international practices have, however, failed to grasp the inherent instability of practice. We argue that this failure is due to a particular conception of change that can be found in the works of Pierre Bourdieu. Through a close reading of Pouliot’s Bourdieusian analysis of post-Cold War politics, we demonstrate the limitations of such a perspective, notably that it is unable to grasp how change originates in practice.