This week, world powers and Iran may well be poised to reach an historic agreement to limit the Islamic Republic’s nuclear program—a diplomatic feat that promises to reorder the Middle East and neutralize a threat that has loomed over the region for a decade.

The talks, held in Geneva, will be the third in the Swiss city since the inauguration of Hassan Rouhani, who in September became the first Iranian president to speak with his American counterpart in 34 years when he chatted on the phone with President Barack Obama.

Key to successful talks will be direct engagement between U.S. and Iranian diplomats, a fraught enterprise with a long history of false starts, missed opportunities and failures to communicate. But for all the suggestion that these negotiations might be different, there’s ample reason to worry that the same mistrust that scuttled past efforts will do so once again.

There’s no question that Rouhani’s phone call with Obama was significant—a dramatic breakthrough that opened some space for diplomacy. Even more significant have been the hours of direct talks between Iranian Foreign Minister Mohammad Javad Zarif and Secretary of State John Kerry. Yet this is not the first high-level contact between these two bitter adversaries. Even the George W. Bush administration sought to engage Iran, former top Bush officials insisted in recent interviews, and achieved some limited results. What follows is an accounting of the diplomatic feints, partial victories, misunderstandings and might-have-beens that brought us to today.

***

The first encounter following the 1979 revolution did not set a happy precedent. Islamic Iran’s first foreign minister, Ebrahim Yazdi, met Secretary of State Cyrus Vance on the sidelines of the U.N. General Assembly in October 1979 and recited a litany of grievances, recalls John Limbert, a former U.S. diplomat in Iran. Yazdi resigned a month later after radical students seized the U.S. Embassy and held 52 Americans—including Limbert—hostage for 444 days. The Iranian government subsequently outlawed Yazdi’s Freedom Party and the Texas-educated pharmacologist was incarcerated several times in Tehran’s Evin prison.

The most notorious talks took place in 1986, of course, when then national security adviser Robert “Bud” McFarlane led a small group to Tehran to sell U.S. arms in return for Iranian help in releasing U.S. hostages in Lebanon. Among the Iranians they met was none other than Rouhani, who, like the fictional character Zelig, appears to have been present at most crucial moments in Iranian foreign policy since 1979. The visit and the arms shipments were subsequently revealed by a Lebanese publication and dubbed the “Iran-Contra” scandal; the Ronald Reagan administration had illegally used proceeds from the arms sales to fund anti-communist guerrillas in Nicaragua.

President George H.W. Bush got off to a more auspicious start when he promised that “goodwill begets goodwill” in his inaugural address—a message clearly aimed at Iran. But direct talks eluded him. Bush once got hoodwinked into thinking that an Iranian he was talking to on the phone was his counterpart Akhbar Hashemi Rafsanjani; the caller turned out to be an imposter. New York Times reporter Elaine Sciolino, who wrote about the episode in 1997, said that Bush spoke to the man through an interpreter for more than 30 minutes and that the White House only realized it was a hoax when Iranian state radio failed to broadcast a promised message on Iran’s desire for better relations.

Rafsanjani’s reformist successor, Mohammad Khatami, came into office seeking to “break down the bulky wall of mistrust” with the United States but could not bring himself to shake President Bill Clinton’s hand on the sidelines of the U.N. General Assembly in the fall of 2000 despite a speech by Secretary of State Madeleine Albright a few months earlier expressing regret for the CIA’s role in a 1953 coup and for U.S. support of Saddam Hussein in the 1980-88 Iran-Iraq war.

It took the 9/11 attacks to break the ice. Iranians, virtually alone among Muslim-majority countries, expressed sympathy for the victims, and Supreme Leader Ayatollah Ali Khamenei even suspended the usual “Death to America” chants at Friday prayers. The United States and Iran also shared the geopolitical aim of removing the Taliban regime in Afghanistan. As I detailed in my 2007 book, Bitter Friends, Bosom Enemies: Iran, the U.S. and the Twisted Path to Confrontation, talks went beyond the Bonn conference of December 2001. Using as cover a U.N. process on Afghanistan that had begun in 1997, American and Iranian officials held more than a dozen meetings from the fall of 2001 through May 2003 in Paris and Geneva. To sustain the cover, talks would start at U.N. offices in Geneva or the Paris apartment of Lakhdar Brahimi, then the U.N. secretary general’s special envoy for Afghanistan. Afterwards, U.S. and Iranian diplomats sojourned to the Intercontinental Hotel in Geneva or the Marriott in Paris to continue the conversations over soft drinks and potato chips. While Afghanistan was the initial focus, later topics included al Qaeda fugitives fleeing into Iran and the U.S. buildup to invading Iraq.

Retired U.S. diplomat Ryan Crocker, who participated in those talks, told me that at their first Brahimi-chaperoned meeting after 9/11, a senior Iranian envoy, whose name remains confidential, “proposed we go off and have a quiet cup of coffee.” Crocker found the Iranians “very positive and forthcoming and really interested in what we could put together in Afghanistan that would be better for both of us,” he said. Iran, which had almost gone to war with the Taliban in 1998 after the radical faction murdered eight Iranian diplomats and a journalist in the northern Afghan city of Mazar-e Sharif, was “very anxious for us to get on with the war,” Crocker noted, going so far as to provide the United States with accurate maps of Taliban positions (as opposed to the Pakistanis, who tried to get the Americans to bomb the anti-Taliban Northern Alliance).

Crocker, whose first posting was in Iran before the revolution, took part in most of the meetings with the Iranians. Hillary Mann (now Hillary Mann Leverett), at the time a staffer on the White House National Security Council (NSC), participated in several sessions; Zalmay Khalilzad, also at the NSC but later ambassador to Afghanistan, Iraq and the U.N., was in the last two meetings. On the Iranian side were several senior diplomats including, for the final three meetings, Zarif, then Iran’s U.N. ambassador. One round of talks in February 2002 was cancelled after President Bush called Iran a member of an “axis of evil” in his State of the Union address, but talks resumed—contrary to what the New Yorker’s Dexter Filkins wrote recently—although they were less productive.

The talks ended in May 2003 after they leaked to the press, and after bombings took place in Saudi Arabia that the Bush administration alleged were planned by al Qaeda figures under “hotel arrest” in Iran. But Crocker, Mann, Khalilzad and former Secretary of State Colin Powell have all described the U.S.-Iran conversations as useful—Powell told me in 2006 that they “should have been restarted.” Several hundred al Qaeda fugitives who had fled from Afghanistan were arrested and deported by the Iranians, according to Mann. Crocker said those turned over included a senior al Qaeda facilitator based in the eastern Iranian city of Mashhad. Zarif, in the final meetings, warned the Americans prophetically about the problems the United States was likely to face in Iraq, Khalilzad acknowledged in 2006.

“After the ‘axis of evil’ [speech], the heart went out of the negotiations,” Crocker told me. “The Supreme Leader and [Quds Force chief] Qassem Suleimani … wrote us off,” Crocker said, apparently no longer believing that the United States was prepared to end its hostility toward Iran despite Iran’s help in Afghanistan. “The talks did go on but they were stilted and non-substantive,” Crocker added, describing them as “an exchange of assertions, allegations and denials.”

Around the time this channel was closing, Iran’s ambassador to France, Sadegh Kharrazi, Zarif and the Swiss ambassador to Tehran, Tim Guldimann, drafted an agenda for comprehensive negotiations that the Swiss delivered to the State Department. The Bush administration, full of hubris after toppling its second government in two years, did not reply to what has become known as the “grand bargain” proposal. Some U.S. officials questioned whether the agenda had Khamenei’s all-important backing. Others thought the United States could stabilize Iraq without Iranian help and that Iran’s government – in the words of Bush appointee John Bolton – should “take a number” and might be the next to fall. The United States further alienated the Iranians by breaking a pledge to declare members of the Mujahedin-e Khalq – an anti-Iran militant group based in Iraq that was on the State Department terrorist list – as enemy combatants. Iran gave the green light to its numerous Shiite proxies in Iraq to attack American soldiers, who became bogged down in a multi-sided civil war.