When Barack Obama left to visit Israel in March, expectations could hardly have been lower. He had a relationship with Prime Minister Benjamin Netanyahu that was widely described as “frosty.” The two had feuded over everything from Obama’s insistence, early in his first term, that Israel freeze settlement building to Netanyahu’s repeated threat to bomb Iran unilaterally. The rapport between them was so strained that Netanyahu had all but openly rooted for Mitt Romney to win in November.

The Israeli public, too, viewed Obama with suspicion. He had not visited Israel in his first term, and in his famous 2009 Cairo speech, he was said to have argued that the Holocaust justified Israel’s creation, a grave insult to a country that bases its right to exist on the Jewish people’s historic and uninterrupted presence in the Holy Land. That Obama had not in fact said this in Cairo, that other presidents had waited until their second term to visit Israel, and that under Obama military aid to Israel was at a record high did not seem to matter. Polls showed that a sizable portion of Israelis viewed Obama as hostile to their interests and partial to the Palestinians.

The president’s aim during this visit was to turn this unpromising state of affairs around, a fact that became apparent as soon as he exited Air Force One. “I know that in stepping foot on this land, I walk with you on the historic homeland of the Jewish people,” Obama said upon arriving at Ben Gurion Airport—magic words meant to rebut the impression left by his Cairo speech. He would elaborate on that formulation over the next three days, to the delight of Israeli media commentators, underscoring the point with a visit to the tomb of Theodor Herzl.

Before the trip, former U.S. diplomat and Middle East negotiator Aaron David Miller, echoing a widely held view, predicted in the Washington Post that “[t]here isn’t likely to be a dramatic transformation in Obama and Netanyahu’s relationship, and certainly not on this visit.” But in their joint appearances in Israel, the president and Netanyahu—whose power had been weakened in recent Israeli elections even as Obama’s was strengthened in November—were all smiles and pats on the back, conspicuously agreeing with each other’s positions on Iran and Syria, trading jokes about their respective children’s good looks, and displaying such bonhomie that NBC’s Mark Murray called it a “bromance.”

Then came the highlight of the trip, Obama’s address to college students in Jerusalem. The president began the speech by noting the coming of Passover and, to build a connection with his audience, explaining the significance of the Exodus narrative to both African Americans and himself. “For me, personally, growing up in far-flung parts of the world and without firm roots, the story spoke to a yearning within every human being for a home.” He talked of the Jewish people’s centuries of suffering and exile and of the sustaining dream of an independent homeland. He spoke of the struggles and sacrifices of Israel’s founding generation, and praised the country Israelis have built, with its high-tech entrepreneurial economy and its culture of vibrant public debate. He extolled the shared interests and “unbreakable bonds of friendship” between Israel and the U.S.

Most importantly, he described Israel’s security situation as Israelis themselves see it: that the country had taken “risks for peace” by withdrawing from Lebanon and Gaza only to get rocket fire in return; that its diplomatic entreaties have too often been met by rejection and anti-Semitism; and that the skepticism toward the peace process felt by many Israelis, especially the younger generation, was completely understandable.

Then, after portraying the world as seen through Israeli eyes, he asked his audience to see through Palestinian eyes—their lives hemmed in by an occupying army, unable to move about freely or farm their lands, subject to attacks by settlers that go unpunished. “Just as Israelis built a state in their homeland, Palestinians have a right to be a free people in their own land,” he said, linking the Zionist vision he’d just acclaimed to an argument for the renewal of the peace process. His supposedly jaded young audience roared with approval.

“This will not be the same country after this speech,” gushed Haartz columnist Bradley Burston that night. A week later, a Jerusalem Post poll found that the percentage of Israelis who consider Obama more pro-Palestinian than pro-Israel had fallen from 36 to 16 percent.

The question now is whether Obama can or will leverage his enhanced stature into peace negotiations that will go anywhere. No one has ever lost money betting against the Palestinian-Israeli peace process, and there are good reasons to be doubtful now—not the least of which is that Netanyahu’s governing coalition, which contains representatives of the pro-settler Jewish Home Party, would likely fall apart if pressed to accept concessions to the Palestinians.

That said, it is possible for one presidential trip to change the dynamics of seemingly unyielding geopolitical problems. I’ve witnessed it myself.

In November of 1999, President Bill Clinton flew to Turkey and Greece on a trip aimed at easing tensions in the broader Balkan region, and in particular between those two countries. As the Greek American on Clinton’s speechwriting staff, it fell to me to write the address he would give in Athens. The Greek-Turkish problem was not nearly as geostrategically important as the Israel-Palestine situation, but it seemed no less intractable. Sparked by the 1974 Turkish invasion of Cyprus, it had roots in the Ottoman occupation of Greek lands centuries before. As recently as 1996, the Greek and Turkish militaries had almost come to blows over the disputed sovereignty of an uninhabited Aegean islet; Clinton himself had had to talk the two countries into holstering their weapons.

Then, in the summer of 1999, Turkey was hit by a devastating earthquake, and the Greeks responded by sending badly needed humanitarian aid—a spontaneous outpouring of sympathy that surprised both sides. A few months later, Greece itself suffered an earthquake, and Turkey responded with assistance. Seizing the moment, the two countries’ foreign ministers, Ismail Cem of Turkey and George Papandreou of Greece, began a round of “seismic diplomacy” meant to explore more permanent ways of building trust. Chief among these was a deal the Clinton administration had been advocating: Greece would end its objection to Turkey becoming a candidate for membership in the European Union, something Turkey desperately wanted. In return, Turkey would amend its constitution to better protect its minorities (including its shrinking Greek population), reduce the role of the Turkish military in civilian politics, and press for a negotiated end to the division of Cyprus that would include the removal of Turkish troops from the island.

None of this was likely to happen, however, without sustained U.S. involvement, and there were two major obstacles to that. The first was a profound undercurrent of anti-Americanism in Greece that dated back to the U.S. government’s ill-advised support for the military junta that ran Greece from 1967 to 1974. The second was Kosovo. In 1998, the U.S. led a NATO bombing campaign against Slobodan Milosevic’s Serbia that pushed Serb forces out of Kosovo and allowed hundreds of thousands of Kosovo Albanians to return to their homes. Though Greece, a member of NATO, had not stood in the way of the bombing, average Greeks, who generally sympathized with their fellow Orthodox Christian Serbs, were infuriated by it. That fury was focused directly on Clinton.

I was working in the White House at the time of the Kosovo campaign, and remember getting a call from a cousin of mine in Athens, whom I adore, pleading with me to do something to get my boss to end his “crimes against humanity.” I did not share her opinion, having seen Milosevic’s handiwork up close as a journalist in Bosnia. But as I worked on the Athens speech in an Istanbul hotel room on our way to Greece I tried to convey some empathetic understanding of her distress. The Greek leg of the trip was scheduled to last two days, but had been reduced to one after the Greek government said it could not guarantee the president’s safety—such was the depth of Greek anger. As Air Force One descended at night into Athens, we could see out the windows the glow of fires from downtown storefronts set ablaze by leftists protesting the president’s visit.

The next day, Clinton gave a speech that, like Obama’s Jerusalem address, began by expressing his personal identification with his audience. He spoke of gifts of democracy and learning that ancient Greece had given the world, quoting the poet Shelley’s famous line “We are all Greeks.” He hailed the vitality and success of the Greek American community and their contributions to the United States, singling out his boyhood friend from Arkansas, David Leopoulis, “who, after forty-five years, still every single week sends me an email about Greece and Greek issues to make sure I don’t stray too far from the fold.” (That last line, with its charming mix of ingratiation and authenticity, was, of course, ad-libbed.) He detailed the long history of friendship between the United States and Greece, including fighting as allies in World War II.

And then he said this:

When the junta took over in 1967 here, the United States allowed its interests in prosecuting the Cold War to prevail over its interests—I should say, its obligation—to support democracy, which was, after all, the cause for which we fought the Cold War. It is important that we acknowledge that.

With those two sentences—still remembered today in Greece as an apology, though in fact it stopped short of that—the president managed to lower the defenses of the entire Greek population, just as Obama’s defense of Zionism would later do in Israel. That made Greek listeners open to hearing the rest of his speech, which was an extended argument for Greece to take the lead in promoting stability and democracy in the region and bridging ethnic and religious divides, especially between itself and Turkey. “We can never wholly forget the injustices done to us, nor can we ever escape reminders of the mistakes we, ourselves, have made,” Clinton said, his words applicable to both his own country and his audience’s. “But it is possible to be shaped by history without being a prisoner to it.”

The speech was an enormous success, hailed by pundits who had only recently condemned Clinton. “The impact, I hope, is that people in our country too will realize that it’s good to look back on our own history and recognize our errors,” a leading Greek think tank scholar, Ted Couloumbis, told the Los Angeles Times. “It takes the capacity to be self-critical to begin settling our own problems with our adversaries.”

A month later, the Greek government dropped its veto of Turkey’s EU candidacy, a risky move domestically but one made less politically painful by Clinton’s speech. Today, tensions between Greece and Turkey still exist, but they are a fraction of what they once were.

This was not the only time Clinton used his rhetorical skills to alter seemingly intractable geostrategic realities. His 1995 speech in Belfast paved the way for the Good Friday Accords, and his 2000 speech before the Indian parliament launched a new strategic partnership between the world’s two biggest democracies, estranged during the Cold War.

The Israel-Palestine conflict may be far more insoluble than these other situations. But in sizing up the possibilities, don’t underestimate the considerable diplomatic power of an inspired presidential speech. That’s what Barack Obama delivered in Israel.

Paul Glastris

Paul Glastris is the editor in chief of the Washington Monthly. A former speechwriter for President Bill Clinton, he is writing a book on America’s involvement in the Greek War of Independence.