Focusing on the development of travel between the borderlands of Ukraine and Soviet satellite states in Eastern Europe, this article explores what it meant to be Soviet outside the Russian core of the USSR between the mid-1950s and the mid-1980s. The cautious opening of the Soviet border was part of a larger attempt to find fresh sources of popular support and enthusiasm for the regime's “communist” project. Before the Prague Spring of 1968 in particular, official policies and narratives of travel thus praised local inhabitants who crossed the Soviet border for supposedly overcoming age-old hatreds to build a brighter future in Eastern Europe. By the 1970s, however, smuggling and cultural consumption discredited the idea of “internationalist friendship.” This encouraged residents of Ukraine to speak and write about the continuing importance of the Soviet border. The very idea of Sovietness was defined in national terms, as narratives of travel emphasized that Soviet citizens were inherently different from ethno-national groups in the people's democracies. Eastern Europe thus emerged as an “other” that highlighted the Soviet character of territories incorporated into the USSR after 1939, helping to obscure western Ukraine's troubled past and leading to the emergence of new social hierarchies in the region.