Since the early 2000s, “soft power” has become one of the most popular analytical tools in International Relations scholarship devoted to analyzing the influence of states in the international arena. Although scholars of Russian foreign policy have also embraced the notion of “soft power”, they have mainly limited the scope of their analysis to Western countries and the former Soviet republics. In contrast, this article focuses on Laos, Vietnam and Thailand, countries whose history of relations with Russia are fundamentally different from both the West and Russia’s “near abroad”. By analyzing the images of Russia and its soft power resources in these countries, this article seeks to create a more comprehensive understanding of the ways contemporary Russia is perceived in the world and its potential tools of influence in Southeast Asia. Drawing on the results of a survey conducted among university students, this article examines the ways young educated elites in the three countries perceive Russia. It also explores the degree of correspondence between these images and the self-image of Russia espoused by its political elites. The results of this study suggest that while overall Russia is perceived as a Great Power, and its role in the world is seen as mostly positive, there are also important dissonances between the two images. Based on discernible differences among the three groups of respondents in the ways they perceive Russia, the article also suggests that historical memory plays an important role in shaping these perceptions.