The more relaxed border regime shows how values and interests can be reconciled. Young Kaliningraders who opt to study in Poland with EU grants are bound to become aware of the political, social, and economic benefits of the EU. These are values that the Polish government wants to share with its Eastern neighbors.

As for Warsaw’s interests, there is a direct economic and security benefit to having a neighboring territory like Kaliningrad become more open and more prosperous.

Russia found it much more difficult than Poland to agree to the new regime. Hardliners in Moscow feared that allowing Kaliningraders to travel freely into the EU would wean them away from Russia. Kaliningrad, the former German city of Königsberg, is the last bit of territory the Red Army conquered in World War II that Russia has not lost after the end of the Cold War. As such, it has a particular symbolic importance.

Yet Russia had good reasons to take the risk of liberalizing the border regime. President Vladimir Putin has been asking the EU for years to exempt all Russians from visa requirements.

The EU refused because several member states don’t consider Russia’s borders secure enough. And, besides, if Russia were granted that right, other non-EU countries, especially Ukraine, would demand visa-free travel for their citizens, too.

By allowing Kaliningraders to travel freely, Russia wanted to prove that it could manage its borders in a responsible manner.

Poland’s Foreign Minister Radek Sikorski had lobbied Brussels long and hard for this special arrangement. Now that he has achieved it, with Germany’s support, he has moved on to other issues—again involving Kaliningrad.

At a meeting last week in Warsaw with the foreign ministers of Russia and Germany, Sergei Lavrov and Guido Westerwelle, Sikorski discussed what to do with the enormous quantities of Cold War munitions that are still stored in Kaliningrad.

According to estimates, there are 100,000 tons of unexploded ordnance that have yet to be disposed of.

Poland hopes that an agreement on destroying these munitions may pave the way for further progress on Kaliningrad. The most important—and most difficult—issue is the stationing of missiles in the exclave. Russia had announced its intention to base both surface-to-air and ballistic missiles there in response to NATO’s planned missile-defense systems. Warsaw now hopes that better bilateral ties might make Moscow at least reconsider. But everyone knows that also depends on U.S.-Russian relations.

None of this progress would have been possible if Poland’s center-right government had not decided to change its stance on Russia.

Until recently, that relationship was rooted in animosity and distrust—hardly surprising after the decades that Poles spent under Soviet occupation.

Those feelings have not disappeared. But instead of letting them paralyze the relationship with Russia, Poland now has adopted a strategic approach toward the Kremlin.

That is not just because Poland is a strong, articulate, and confident member of the EU, aware that its EU membership will help it to defend its interests. It is because Prime Minister Donald Tusk’s center-right government realized that it could balance its values with its interests when dealing with Russia, as the case of Kaliningrad shows.

That is a rare achievement, and one that the rest of Europe would do well to take to heart.