Little empirical research has considered the way in which macro-regions are perceived outside academic and political circles. Such studies alone can determine what regional narratives mean for the wider public, and the extent to which they coincide with region-building images produced by elites. This article examines the mental maps of high school seniors in 10 cities in the Baltic Sea and Mediterranean regions, focusing upon their perception and knowledge of other countries in those areas. Despite efforts at region building since the Cold War, the two regions remain divided on mental maps. Students have little knowledge of countries across the sea from their own, although such knowledge is generally greater among those from coastal (and particularly island) locations. A comparison with maps constructed by Gould in 1966 reveals that the perception of countries within one's own region among Italian and Swedish students has become more negative over the last 50 years.