AMMAN, Jordan (AP) Democratic presidential contender Barack Obama stepped into the thicket of Mideast politics Tuesday, declaring in Jordan that neither the Israelis nor the Palestinians are strong enough internally to make the bold concessions necessary for peace.

Obama said he would work to bring the two sides together "starting from the minute I'm sworn into office." But he cautioned it is "unrealistic to expect that a U.S. president alone can suddenly snap his fingers and bring about peace in this region."

After meeting with Jordan's King Abdullah II, Obama flew to Israel for talks with Israeli leaders. He'll also meet with Palestinians.

Upon his arrival in Jerusalem, he spoke of a "historic and special relationship between the United States and Israel, one that cannot be broken" and one that he hoped to strengthen as president.

In Jordan, he made his comments on the struggle for Mideast peace within a few hours of stepping off a military aircraft -- a presidential contender carrying body armor and wearing orange earplugs -- following his tour of war zones in Afghanistan and Iraq with two fellow senators.

Standing alongside ancient mountaintop ruins with the Amman city skyline his memorable backdrop, Obama declined repeatedly to concede that President Bush's decision to dispatch 30,000 troops to Iraq in 2007 had succeeded. Still, he said, "I believe that the situation in Iraq is more secure than it was a year and a half ago."

The Illinois Democrat predicted at the time the troop increase was begun that it would not succeed.

On Tuesday, he also stood by his call for the withdrawal of U.S. combat forces from Iraq over a 16-month period and said the United States, NATO and the Afghanistan government must do more to counter a resurgent Taliban and al-Qaida.

Back home, Republican rival John McCain renewed his criticism of Obama's pledge to pull U.S. combat troops out of Iraq by the second year of his administration if he wins the presidency.

"Sen. Obama would rather lose a war in order to win a political campaign," McCain said at a town hall meeting in Rochester, N.H.

Jordan was the initial stop of a second stage of Obama's international trip, this part financed by his presidential campaign after the official congressional visit to the war zones with fellow senators.

Obama has been to the Middle East before, but not as the Democratic presidential nominee-in-waiting, and his Jordanian hosts seemed eager to prepare a warm greeting.

King Abdullah flew back from Colorado for the visit, and Obama aides said the Jordanians had suggested a one-on-one meeting before the two were joined by a larger group for dinner at the palace. The king later drove his guest to the airport in his Mercedes.

Following dinner, Obama flew aboard his newly refurbished chartered campaign jet to Israel for meetings with Israeli leaders as well as Palestinian President Mahmoud Abbas in Ramallah on the West Bank. After that he was to visit Sderot, an Israeli town under periodic shelling from Palestinian militants in the nearby Gaza strip.

Obama said that an ultimate resolution in the region is going to involve "two states standing side-by-side in peace and security and that the Israelis and the Palestinians are going to both have to make compromises in order to arrive at that two-state solution."

Yet, he added, "One of the difficulties that we have right now is that in order to make those compromises you have to have strong support from your people. And the Israeli government right now is unsettled. ...

"The Palestinians are divided between Fatah and Hamas. And so it's difficult for either side to make the bold move that would bring about peace the way, for example, the peace between Israel and Egypt was brought about. Those leaders were in a much stronger position to initiate that kind of peace."

In particular, he said the United States should create "a greater sense of security among the Israelis, a greater sense that economic progress and increased freedom of movement is something that can be accomplished in the Palestinian territories and, with those confidence-building measures, that we get discussions back on track."

Jordan's king told Obama that an evenhanded U.S. policy would bolster America's credibility in the Middle East and that achieving Palestinian statehood was essential for ending the Arab-Israeli conflict, according to a royal palace statement summarizing Abdullah's remarks during their private meeting.

In Israel, Obama also was expected to stop at Yad Vashem, the memorial to victims of the Holocaust, and possibly the Western Wall, the site of an ancient temple and Judaism's holiest place.

At its political core, Obama's trip is designed to reassure skeptical voters about his ability to function as commander in chief and to forge a new foreign policy after eight years of the Bush administration.

Jewish voters in the U.S. are among those Obama is seeking to impress. He trailed Sen. Hillary Rodham Clinton among them during the Democratic primaries, although he has made inroads in recent weeks.

Asked about stronger support among Israeli Jews for Republican candidate John McCain, Obama told CBS News that's because his rival is better known.

"People just don't know me as well," Obama said. "That's part of the reason why we're going to spend a day visiting there in discussions and hopefully give people confidence that I have a track record that will assure not only the people of Israel, but friends of Israel back home, that, in fact, Israel's security is paramount."

He steered well clear of explicitly criticizing Bush in his Mideast comments, although he said, "What a U.S. president can do is apply sustained energy and focus on the issues of the Israelis and the Palestinians."

The administration has been prodding the two sides toward a compromise in its final months in office, but has come under criticism from some for not making it a stronger priority earlier.

In comments on his trip to Iraq, Obama acknowledged that Gen. David Petraeus, the overall commander of U.S. forces in Iraq, had concerns about a fixed timetable for withdrawal.

He expressed sympathy with that view, though he made it clear his outlook would be a broader one.

"I think he wants maximum flexibility to be able to -- to do what he believes needs to be done inside of Iraq," Obama said, "But keep in mind, for example, one of Gen. Petraeus' responsibilities is not to think about how could we be using some of that $10 billion a month to shore up a U.S. economy that is really hurting right now. If I'm president of the United States, that is part of my responsibility."

After leaving Israel, Obama flies to Germany, France and England before returning to the United States next weekend.

Before Obama arrived in Jerusalem, a Palestinian rammed a construction truck into three cars and a bus near the hotel where he was to stay, injuring five people before an Israeli civilian shot and killed the attacker.

Abbas condemned the attack. And Obama, speaking from Jordan before leaving for Israel, called it "a reminder of what Israelis have courageously lived with on a daily basis for far too long."

"I will always support Israel in confronting terrorism and pursuing everlasting peace and security," Obama said.