In the 20th century, relations between Japan and Southeast Asia experienced several dramatic ups and downs. Japan was the first non- European country that in the late 1930s presented its own vision of the regional order in Asia. The consequences of its implementation proved to be painful both for Japan itself and for its neighbors. After the Japanese defeat in World War II, the historical memory of Japan as an aggressor became part of political and social consciousness of many states of the region. However, in the second part of the 20th century, Japan managed to transform radically this perception in Southeast Asia, turning itself into a leading macro-regional power. This transformation did not come without difficulties but eventually resulted in a successful overcoming of the World War II legacy and made Japan one of the most welcomed alternative forces amidst the rising Sino- US contradictions. A new wave of proactive relations between Japan and Southeast Asia took place against the background of China’s economic rise and was connected with the advancement of the Japanese version of the Indo- Pacific as a reaction to China’s rise. This article argues that Japan’s success in its relations with Southeast Asia had several reasons. The first one was the reassessment of the Japanese structural role in the region (from a militarist force imposing a hierarchical regional order into a power which managed to organize regional development based on the network type of connections). Others included the progressive dynamics of institutional interaction with ASEAN and targeted cooperation  in the areas where Japanese interests coincided or were significantly  close to the interests of Southeast Asian states. Despite the fact that Russia can hardly repeat Japanese success in developing its relations with Southeast Asia, certain elements of it are well worth taking note of.