We're somewhere over the Mediterranean, and Mahmoud Abbas, the Palestinian president, is trying to get inside the head of Barack Obama. "We knew him before he became president," he's saying, struggling to understand what happened to the man who had seemed more sympathetic to the Palestinian cause than any of his predecessors. "We knew him and he was very receptive." Around us, Abbas's closest aides are shuffling papers or typing on laptops, while his bodyguards lounge on long corduroy couches. Saeb Erekat, the ubiquitous adviser, is writing talking points for Abbas's meeting the next day with French President Nicolas Sarkozy. A man with a sidearm is shoveling pumpkin seeds into his mouth. In a space the size of two living rooms, most of the 20-odd passengers are puffing on cigarettes, and so is Abbas. At 76, he smokes more than two packs a day.

Abbas is about as affable as politicians come—even hawkish Israelis like Ariel Sharon have said so. But occasionally, he can deliver a shot of scathing criticism, usually followed by a grandfatherly smile. A week earlier, he told me bluntly that Obama had led him on, and then let him down by failing to keep pressure on Israeli Prime Minister Benjamin Netanyahu for a moratorium on settlement building in the West Bank last year. "It was Obama who suggested a full settlement freeze," Abbas explained. "I said OK, I accept. We both went up the tree. After that, he came down with a ladder and he removed the ladder and said to me, jump. Three times he did it." Abbas also criticized the mediation efforts of Obama's special envoy, George Mitchell, who has shuttled between Israelis and Palestinians for more than two years. "Every visit by Mitchell, we talked to him and gave him some ideas. At the end we discovered that he didn't convey any of these ideas to the Israelis. What does it mean?"

Now, on the flight from Tunis to Paris, I wanted to know how long Abbas could wait. The next 18 months are probably dead time in Israeli-Palestinian diplomacy as Obama focuses on his reelection campaign. No candidate for president wants to risk alienating Israel's supporters by pressing the peace question. But a second-term president can be bolder. Bill Clinton, after his reelection in 1996, managed to get an Israeli agreement for a partial West Bank withdrawal. Netanyahu remembers it well: He was prime minister at the time. But Abbas, who has worked every angle for Palestinian statehood for 50 years, the last six as president, says he's nearly out of time. "I cannot wait. Somebody will wait instead of me," he tells me. "And I will not stay more."

As the Middle East undergoes profound transformation, Americans can count on one thing in the region remaining the same: The unresolved Israeli-Palestinian conflict will continue to be an irritant for Arabs and a source of resentment against the United States. Abbas offered the best hope for peace between the two sides when he took over for Yasir Arafat in 2004. Moderate in his approach to Israel and unequivocally against violence, he was the counterpoint to Arafat's wiliness and eccentricity.

The optimism didn't last long. In short order, Abbas lost his parliament to the Islamists of Hamas and then lost Gaza to the same uncompromising group. By the time he and Prime Minister Ehud Olmert drew close to agreement in 2008, corruption charges made the Israeli leader a lame duck. Then Israelis elected Netanyahu.

If Abbas leaves the stage without a deal, it would add another layer of uncertainty to the regional turbulence. Among political figures in the West Bank and Gaza, Abbas is the most popular, followed by the leader of Hamas. Even if Abbas's Fatah party can retain power, his successor would lack Abbas's founding-generation stature. He would likely be less able to push through the required compromises for peace with Israel. "It would really be a tragedy of missed opportunities," says Yossi Beilin, a former peace negotiator who knows Abbas well.

While these issues swirl, Abbas last week let Newsweek into his personal space. For five days, I traveled with him from Jordan to Tunisia to France as he rallied support for a U.N. resolution this September that would confer statehood on the Palestinians—a conscious replication of the process that gave birth to Israel more than 60 years ago. On the plane and before and after the meetings, I had almost unfettered access to Abbas and his closest advisers.

The team travels on an Airbus A318 borrowed from the United Arab Emirates (the PLO owns just a tiny jet). When fitted for commercial flights, it holds 132 passengers, but in the current configuration, it has all the comforts of a private plane: open spaces, wood-topped coffee tables, and leather bucket seats. Abbas's travel routine includes a few moments of prayer in his seat during takeoff and then about 15 minutes of reading from a dog-eared copy of the Koran. Through much of the flight, stewardesses are wheeling out Middle East staples like couscous and kebabs but also shrimp and calamari and mussels, which Abbas seems to particularly like. As we're landing in Tunis, an aide who'd introduced himself as Colonel Said goes around spraying Paco Rabanne Ultraviolet on each of the passengers.

The trip has all the trappings of a foreign tour by a head of state: the presidential marching bands at the airports and the convoys of black luxury cars speeding through town as policemen hold up traffic (in Paris, no less). They're a testament to the juggernaut the PLO has built up over many decades, and the broad sympathy governments have for the Palestinian cause. But Abbas is constantly aware that he heads something short of a state, and that the time left for him to achieve independence is ticking down.

On the evening of Feb. 17, Abbas got a phone call to his office in Ramallah. President Obama was on the line with a request. In the preceding weeks, Arab protesters in the region had toppled two longtime autocrats, including one of America's closest Arab friends, Hosni Mubarak. Demonstrations raged in Libya and Yemen, and would soon spread to Syria. In Washington, officials worried that the protesters would eventually focus on America's relationship with some of these dictators and on its support for Israel. Obama's cautious steps seemed to be preventing the dreaded scenes of protesters burning American flags. But a U.N. Security Council resolution initiated by Palestinians and scheduled to be debated the next day threatened to remind Arabs of the very thing they hate most about America.

The resolution demanded that Israel "immediately and completely cease all settlement activities in the occupied Palestinian territory," a position Obama long supported. In fact, Palestinians say they lifted the language straight from public remarks made by Secretary of State Hillary Clinton. But it put Obama in a bind. Members of his Democratic Party felt they'd paid a price in the midterm elections a few months earlier for Obama's tough stand with Netanyahu in the preceding year. An American veto might mitigate the damage. But it would also remind the Arab demonstrators how uncritical America's support for Israel can often be.

So for 55 minutes on the phone, Obama first reasoned with and then pressured Abbas to withdraw the resolution. "He said it's better for you and for us and for our relations," says Abbas. Then the American president politely made what Abbas describes as a "list of sanctions" Palestinians would endure if the vote went ahead. Among other things, he warned that Congress would not approve the $475 million in aid America gives the Palestinians.

Abbas relates the story to me during our stop in Tunis. In the presidential guest house, a sprawling compound of luxurious suites and chandeliered meeting rooms, the televisions are all tuned to the Arabic news networks. In this news cycle, the focus is Syria, where Bashar al-Assad has launched a violent crackdown against protesters. The Palestinians in the room are all rooting against Assad, who has given money and support to Abbas's rivals in Hamas. Earlier in the week, the conversation with Abbas had turned to Mubarak and America's handling of the revolution in Egypt. Abbas told me he thought the push Obama gave Mubarak was "impolite" and imprudent. "From day one, when it started with Mubarak, I had a telephone call with Madame Clinton. I told her, 'Do you know what are the consequences? Either chaos, or Muslim Brotherhood or both,'?" he says. "Now they have both."

After Abbas informed Obama he wouldn't withdraw the resolution, Clinton followed up with a 30-minute exhortation of her own. Then more pressure. Lower-level officials phoned several Palestinian influentials in Ramallah and asked them to use their sway over the Palestinian leader. Still, Abbas was unprepared for what was coming. Only when he watched the Security Council vote on television did the reality sink in. "I had an idea that they will abstain," he tells me. "But when they said, 'Who will be against?' my friend Susan [America's ambassador to the U.N., Susan Rice] raises her hand." Abbas shakes his arm and lets out a long hoot. The council's 14 other members, including France and Germany, all supported the resolution.

Late last week, when Newsweek's White House reporter asked a spokesman for a response to Abbas's criticism, a senior administration official who had been in the room during Obama's conversation with Abbas described the account as a "selective reading of how those events transpired." The official declined to be identified. But Tommy Vietor, a spokesman for Obama's National Security Council, was willing to be quoted by name. He said the conversations with Abbas and Clinton were shorter than Abbas maintains and insisted that Obama did not raise the possibility of punitive measures. "It's simply not accurate to claim that he threatened President Abbas," Vietor said. "President Obama made the same case privately that we make publicly—that this effort does not help the Palestinians, Israelis, or the cause of peace."

The White House also took exception with the notion that Obama left Abbas in the cold; one official called the accusation "nonsense." And Vietor described as "totally inaccurate" Abbas's criticism of Mitchell, the envoy. "Of course he carried both parties' ideas to each other all the time."

In Paris, the French government sends luxury Peugeots to ferry Abbas and his closest aides from Orly airport, while the rest of the entourage gets around in Mercedeses owned by a private car company. My driver tells me the company's owner is a Palestinian who has been friends with Abbas and Arafat since the 1960s. He provides the cars gratis whenever the delegation comes to town. His company also provides service to Arafat's widow, Suha, who lives in Paris and whom my driver describes as "generous with the tips."

We're dropped at the hotel Le Meurice across from the Tuileries Garden. Adjoining suites make up Abbas's room and his office, and aides and guests are constantly coming and going. On the sidewalk outside, a few dozen groupies wait for Beyoncé Knowles, who is also staying at the hotel. She crosses the lobby moments before Abbas heads out to his meetings.

On the agenda with Sarkozy is the outlook for September, when Abbas plans to make his big U.N. gambit. United Nations maneuvering, especially when it relates to the Middle East, is usually the equivalent of a political Ambien. But Abbas believes a resolution that recognizes a new state of Palestine in the 1967 borders would be a game changer, especially if it has the support of the world's leading democracies. Which is why Paris is the fifth European capital he's visited in the past six weeks. Judging by Israel's response, he might not be wrong. In a speech to Israel supporters in New York last month, the usually unflappable defense minister, Ehud Barak, warned that Israel faces deep isolation, a "diplomatic tsunami," come September.

In the room, Sarkozy is receptive. He tells Abbas he's incensed by Israeli Prime Minister Netanyahu's settlement building and supports Palestinian independence. Still, the U.N. vote could draw a harsh Israeli response or trigger another round of violence. After an hour of talks, the French president remains noncommittal.

The strategy for September marks a gamble for Abbas. At least one of his aides worries it will generate the kind of expectation that the Palestinian leader couldn't then meet. U.N. votes don't make 500,000 Jewish settlers suddenly disappear from the West Bank and East Jerusalem. And Netanyahu is unlikely to just hand over the keys. (His spokesman, Mark Regev, said about the U.N. initiative: "The Palestinians can go for more empty rhetoric or choose a path of real change. The only way to peace and Palestinian statehood is through negotiations with Israel.") For the statehood resolution to have more than just symbolic impact, Abbas would have to come back from New York and assert sovereignty over the territory the U.N. just handed him. But that would entail confrontational measures—for instance, ending the security cooperation with Israel. Abbas told me that's a path he will not take.

The danger is that without tangible movement, the disappointment could turn into popular anger—directed at Israel or even at the Palestinian president himself. Abbas is fond of saying that if just 10 people protested outside his office in Ramallah, he would step down, in contrast to the Arab leaders who cling to power. When he told me that on the trip, one of his aides corrected him: "You said three people the last time."

Abbas is missing the tip of his right ring finger. The story I'd heard seemed to reflect the awkwardness Abbas experienced going from being Arafat's behind-the-curtain deputy to leading the PLO—and how much he hated crowds. While campaigning for president after Arafat died in late 2004, a horde of people surrounded his car in southern Gaza. Unsure about their intentions, he pressed the electric button of his armored window and closed it on his own finger. But Abbas told me the real story, a version that made more sense. It was his driver, concerned for his safety, who pressed the button. By the time Abbas reacted, the tip of his finger had been severed.

Abbas was due to give a speech in the town, so he bandaged the finger and stayed for two hours. The same driver then ferried him to a hospital in Gaza City, 30 kilometers away. "I found the doctor there, he made the surgery for me," Abbas told me.

Is the driver still working for him? "No, no, no. I told him, 'You have to leave,' and he left."

With Daniel Stone in Washington and Joanna Chen in Jerusalem