Although the section of the Baltic seashore near Palanga was ceded to Lithuania under the Treaty of Melno, it remained strategically important to the Teutonic Order. From the Middle Ages, the coastal strip of the starostwo of Žemaitija in the Grand Duchy of Lithuania served as a land route connecting the Teutonic Order’s domains in Prussia and Livonia. This article focuses on the dynamics of travel along this route in 1519–1521 when the Teutonic Order was at war with Poland. Although the theatre of war covered areas of Prussia in the triangle between Königsberg, the River Vistula and Mazovia, military escorts used the stretch of land around Palanga to transport messages, carts of ammunition, and soldiers. Mercenaries disguised as merchants, undercover messengers, and sometimes even large formations of soldiers, crossed the coastal strip. Due to the geopolitical situation, the Žemaitijans failed to cut off this movement completely: the Grand Duchy of Lithuania tended to turn a blind eye, and formally adhered to the ‘eternal peace’. This article is the first attempt to shed a light on the role that the Palanga nexus of interaction between Prussia and Livonia played in the 1519–1521 war. It shows the specific participants, the route, and the circumstances of travel through this nexus.