For many, the collapse of Russo-U.S. relations over Moscow’s (bloodless) invasion of Crimea and proxy war in eastern Ukraine points to the beginnings of a new Cold War. However, Russia has not irrevocably transformed itself from limited partner into implacable foe. Washington and Moscow still have many points of shared mutual interest that should not be easily thrown aside in the heat of the moment. Indeed, it’s often forgotten that post–Communist Russia has been engaged with America battling the forces of global terrorism along with efforts to prevent the proliferation of Weapons of Mass Destruction (WMD) to rogue states. Recent happenings elsewhere may create the basis for such a collaboration to be renewed.

As events continue to move quickly in Ukraine, a shocking and potentially game-changing event has occurred in the Middle East. A well-organized and disciplined terrorist organization, ISIS, has attempted to transform itself into a full-fledged terrorist state in parts of Iraq and Syria. Equipped with captured and sophisticated U.S. weaponry as well as huge financial resources sacked from parts of Iraq, ISIS is now attracting thousands of radical young Muslims from around the world. Thanks to its growing resources as well as foreign passports of its soldiers, for the first time in many years, an extremist state possesses the potential capability and will to launch attacks anywhere in the world. The beheading of Jim Foley by a Jihadist with a British accent demonstrates the outreach of ISIS et al in Western Europe, but also America and even in Russia.

Considering the stakes, it would seem both Washington and Moscow could once again find themselves on the same side—possibly working together to diminish the capabilities of ISIS and also other groups such as Al Qaeda and its various offshoots. Assuming a solution in Ukraine can be found, could President Obama shift the Kremlin’s focus from the crisis in Ukraine to a joint new struggle against terrorism?

Putin: Russia’s Christian Autocrat

The first thing Obama must do is attempt to understand what has shaped Putin’s worldview and how this has evolved over time. Although no democratic heart beats in his chest, Putin nevertheless holds some core values similar to many Americans.

Many analysts have focused on Putin having been a junior officer with the KGB in East Germany before the fall of the USSR, and head of the KGB successor, the FSB, in the 1990s. Forgotten by many is that he also served in 1989-94 as deputy to reform-minded St. Petersburg mayor Anatoly Sobchak, and eventually became Yeltsin’s prime minister. The principle architect of Gorbachev’s reforms, Alexander Yakovlev, argued in his memoir, Maelstrom of Memory: From Stolypin to Putin, that Tsar Nicholas II’s prime minister is the best historical analog. Pyotr Stolypin was an autocratic modernizer, and to Yakovlev, Putin was his modern avatar. Rather than a paranoid megalomaniac, Putin is better understood as an ambitious technocrat who aims to restore Russia’s place as a major player in world politics.

Indeed, let us further explore Putin’s role less well known to Americans—that of Christian autocrat—from former servant of atheistic communism to defender of the faith. In May 2001, when President George W. Bush first met Putin in Slovenia, Bush asked him why he was wearing a cross. Putin explained that the cross, given to him by his mother, had been retrieved from a fire in her dacha. Some considered the story “syrupy,” but Bush, who himself had gone through a religious transformation, did not. When asked at a press conference if he trusted Putin, he replied, “Yes, I looked the man in the eye and was able to see his soul.” Russologists for years thereafter dismissed his remark as naive. However, President Bush was not necessarily deceived. True, Putin has not followed the democratic vision of Westernizers like Andrei Sakharov. Rather, he espouses the anti-Bolshevik, religious-nationalist vision of another Russian Nobel Prize winner, the late Alexander Solzhenitsyn. And at times he curiously resembles some on the American right who upbraid cultural decadence and the decline of moral values—a similarity that hasn’t always been lost on them.

In our own search for Putin’s soul, and through many interviews with Russian Orthodox clergy and believers throughout Russia, Europe and the Middle East, we’ve come to regard his embrace of religious orthodoxy as genuine. During his meeting with the pope last year in the Vatican, Putin zeroed in on the plight of the suffering Middle East Christians, and supported the reconciliation of the Western and Eastern branches of Christianity. He is also the only leader in Russia’s long history to visit Jerusalem twice. His own merciless battle against terrorism seems to have provoked sympathy for those of the Jewish faith, and he’s established a friendly and mutually beneficial relationship with Israel.

Putin, Terrorism and NATO Encirclement

At that early meeting with Bush, Putin had vehemently warned the American president about the connections of extremists in the Pakistani intelligence service to Al Qaeda and about a coming “major catastrophe.” Tragically, he was on to something. Condoleezza Rice would later write that “Putin was right…and he never let us forget it.”

The tension that the latter half of Rice’s remark hinted at was real. Unfortunately, the Russian president began to cool towards the United States as new NATO countries began to sprout near Russia’s borders, touching off the traditional Russian fear of encirclement. This anxiety would contribute to the 2008 invasion of Georgia, the 2014 invasion of the Crimea and his intervention by proxy thus far in the Eastern Ukraine.

Yet he was still with America in the struggle against terrorism. In 2011, during the Libyan crisis, the Obama administration persuaded Russia to abstain on the U.N. resolution concerning Libya on the grounds that it also provided for “all necessary means” to prevent the slaughter of civilians. However, the Russians did not want to get rid of Gaddafi, concerned that killing him would provide an opening for the rise of terrorism. As former Russian President, Dmitry Medvedev, explained in March 2011: “If Libya breaks up, and Al Qaeda takes root there, no one will benefit, including us, because the extremists will end up in the North Caucasus.” Putin was right again, and, as with Rice, he’s not letting us forget it. He’s blocked any resolution to dethrone Syrian dictator Bashar Assad. Though there are economic positions that this policy backs up, Russia also has religious concerns. Assad’s Alawite, Shiite Muslim elite was the protector of Syria’s Christians and other minorities. If Assad went, Syria might well become the next Libya—or worse, given the evils that the Islamic State’s fighters gleefully brag about on social media.

Press for a Negotiated Settlement of the Ukraine Conflict

If any possible joint collaboration on defeating the forces of terror is to move forward, a resolution of the Ukraine crisis agreeable to all sides must be found. This doesn’t mean that America must bow to Moscow. To effect a negotiated settlement, Obama should continue to send various types of aid to Kiev, including military aid (as we were among the first to suggest) and even hint that it will increase the military component of such aid in the event of an invasion. This policy should continue as long as Russian armaments are pouring into Donetsk and Lugansk. However, Obama must also put pressure on Kiev to find a negotiated solution with the east Ukrainian separatists. The president can use financial and military aid as inducements to push towards a settlement.

As former Secretary of State Henry Kissinger has advised, negotiating the resolution of a conflict is always better when you’re winning. It is also preferable not to aim for unconditional victory, surrender or annihilation. That was the approach he followed during the 1973 Yom Kippur War. As the Israeli army crossed the Suez Canal and encircled Egyptian forces, Kissinger put pressure on Israel not to annihilate the Egyptian army. He thus found a unique opportunity to forge a solution with Egypt’s patron, Russia, which threatened to intervene to stop Israel’s march. Embarking on shuttle diplomacy with all parties, Dr. Kissinger’s mission proved successful.

The U.S. must likewise put pressure on Kiev not to aim for annihilation of the pro-Russian separatists—as in Egypt, total victory would only increase tension with Russia—but to reach an immediate ceasefire. Diplomatic overtures will hopefully persuade Russia to make the separatists pull in their horns. A negotiated settlement should include amnesty for the separatists, while granting eastern Ukraine autonomy within the federal structure. They should also have full representation in the Ukrainian parliament. Any peaceful resolution of the conflict must also guarantee the sovereign borders of a free and democratic Ukraine, her liberty to join the EU, no NATO membership for Ukraine and no Russian attempts at her destabilization.

While it certainly may be tempting, seeking to humiliate Putin will certainly come at a high price. He must be able to argue he has done all he could to protect Russian speakers in Eastern Ukraine without engineering Russia’s economic decline. Indeed, Putin cannot risk any appearance of being “defeated” in Ukraine. It’s politically dangerous to him—but also to America and the West. A defeat would encourage disintegrative tendencies in Russia—like Siberian and Far Eastern pushes for greater autonomy or Islamic extremism in the North Caucasus and even in the Russian heartland, in places like Tatarstan and Bashkortostan.