Poland's accession to NATO in 1999 undermined Russian-NATO relations. A similar contestation occurred before the EU's eastern enlargement when the transit of Russians to and from Kaliningrad was a contentious topic in EU-Russian diplomacy. Currently Russia's deployment of missiles in Kaliningrad is a security concern. This article argues that NATO's security concerns replaced EU-Russian contestation about visa liberalisation as the main source of conflict in their relationship. It demonstrates that the case of Kaliningrad reflects a dual shift from a contested to a fluid boundary in EU-Russian relations, and from a contested to a solid boundary in NATO-Russian relations.