The historic 2005 Sino-Russian Vladivostok Treaty brought an end to their territorial disputes that had lasted for three centuries. The fact itself that such a longtime historical dispute was settled at all is remarkable. During the Cold War, China and Russia were once on the verge of all-out war in March 1969 when they clashed on Zhenbao Island (Damasky Island) in the Ussuri River. Further clashes in August 1969 along the western section of the Sino-Soviet border in Xinjiang heightened tensions to the extent that the possibility of even a nuclear war was raised. All the more because such a thorny relationship did they experience, the Sino-Russian case is interesting and worthy of scholarly attention (as a clear counterevidence against Ron Hassner’s intractability thesis on “time and the entrenchment of territorial disputes”). This paper, by focusing on a successful case of resolution of Sino-Russian territorial conflicts, tries to get some hopeful suggestions for the ongoing territorial disputes in East Asian international relations, including Korea-Japan territorial disputes. The successful termination of the Sino-Russian territorial disputes itself is not only remarkable, but also is providing hopes for the states and people who are now suffering from territorial disputes. The story of Sino-Russian success in resolving territorial disputes seems to provide the following theoretical or policy implications; (1) The Sino-Russian case suggests that political leadership is very important and a negative bilateral history does not necessarily determine the future of the two countries in a negative way; (2) As Gorbachev demonstrates, unilateral concessions made by a willful political leader could redirect history; (3) Fairness represented by “fifty-fifty” principle is important in solving territorial issues; (4) “Fifty-fifty” principle should not be mechanically applied, but should be applied flexibly; (5) One paradox of Sino-Soviet case is that they were successful in resolving the territorial disputes rather because there are so many flashing points along their border, which made it possible for them to “give and take” more easily and more often than Korea-Japan case, for instance.