Barack Obama pledged support for reconstruction and security efforts in Afghanistan on Saturday, as he opened his weeklong tour of the Middle East, Europe and Afganistan by meeting with U.S. troops and local officials in war-torn regions.

The Illinois senator arrived in Kabul early Saturday for his first-ever visit to Afghanistan, and he next travels to Iraq for the first time as a presidential candidate.

Details out of the first leg of his journey, as part of a taxpayer-funded official delegation, are sparse. But the second leg, which will be paid for by the campaign and take him to five other countries in the Middle East and Europe, is expected to receive intense attention and coverage.

The Illinois senator announced his plans to tour the war zones after facing criticism from John McCain and Republicans. McCain has been to Iraq eight times and last traveled there in March.

The trip affords Obama a unique opportunity to meet not only U.S. commanders on the ground but foreign dignitaries and top U.S. allies -- while the world watches.

Officials say Obama first visited U.S. troops in Kuwait and then headed to Afghanistan Saturday. He met with military leaders and troops at Bagram Air Field, the main U.S. military base in the country, before heading to Jalalabad Air Field, according to a military statement.

The base, in the Nangarhar province, lies near the Tora Bora mountains where Al Qaeda leaders fled and faced a U.S. bombardment during the invasion in late 2001 that ousted the Taliban regime. Usama bin Laden is believed to be in the region, and the militant groups have continued to cause problems.

He and the delegation were briefed by Nangarhar's governor, Gul Agha Sherzai, a bullish former warlord.

"Obama promised us that if he becomes a president in the future, he will support and help Afghanistan not only in its security sector but also in reconstruction, development and economic sector," Sherzai told The Associated Press.

Obama was expected to meet with Afghan President Hamid Karzai on Sunday.

Earlier, Obama met with U.S. troops at Camp Arifjan, the main U.S. military base in Kuwait and gateway for U.S. soldiers heading into and out of Iraq.

He spoke in front of the troops and praised them for their service, while also talking about his strategic goals.

"We've got to have clearer strategic vision that uses all of our power -- our economic power, our diplomatic power, our intellectual power, as well as our military power, to help make this world safer," he said.

Lt. Col. Bill Nutter, a spokesman for the U.S. military in Kuwait, said the officers gave him an overview of operations. Obama shook hands, answered questions, posed for photos and played a little basketball during the visit.

Underscoring the challenges in Afghanistan, authorities reported Saturday that a roadside bomb killed four policemen in the volatile south of the country where the Taliban-led insurgency is intensifying nearly seven years after a U.S.-led invasion ousted the militant movement from power.

Obama advocates ending the U.S. combat role in Iraq by withdrawing troops at the rate of one to two combat brigades a month. He said this past week that the war in Iraq has become a distraction from fighting terrorism in Afghanistan and keeping nuclear weapons out of the hands of rogue regimes.

Obama supports increasing the military commitment to Afghanistan, where the Taliban has been resurgent and Usama bin Laden is believed to be hiding.

Obama told a pair of reporters who accompanied him to his departure from Andrews Air Force Base on Thursday that, "I look forward to seeing what the situation on the ground is.

"I want to, obviously, talk to the commanders and get a sense both in Afghanistan and in Baghdad of, you know, what the most, their biggest concerns are, and I want to thank our troops for the heroic work that they've been doing," he said.

Obama recently chided Karzai and his government, saying it had "not gotten out of the bunker" and helped to organize the country or its political and security institutions.

Also on Obama's itinerary later in the trip is a meeting with Nouri al-Maliki, the Iraqi leader.

Al-Maliki told a German magazine ahead of the meeting that he supports Obama's plan to remove U.S. troops from Iraq within 16 months of taking office. Obama's campaign welcomed the policy endorsement.

Obama has said one benefit of withdrawing U.S. troops is that it would pressure al-Maliki to shore up his government. He said he did not plan to reiterate those messages in person.

"I'm more interested in listening than doing a lot of talking, and I think it's very important to recognize that I'm going over there as a U.S. senator," he said. "We have one president at a time."

McCain, in his radio address released Saturday, criticized Obama for announcing his strategy for both countries before departing on his "fact-finding mission" abroad.

"Apparently, he's confident enough that he won't find any facts that might change his opinion or alter his strategy. Remarkable," McCain said in the address.

And in response to a memo from the Obama camp accusing McCain of following Obama's foreign policy lead, McCain spokesman Tucker Bounds said: "The only reason that the conversation about reducing troop levels in Iraq is happening is because John McCain challenged the failed Rumsfield-strategy in Iraq and argued for the surge strategy that is responsible for the successes we’ve achieved and which Barack Obama opposed."

Traveling with Obama were Sens. Chuck Hagel, a Nebraska Republican and Jack Reed, a Democrat from Rhode Island. The senators, both military veterans, have been mentioned as potential Obama vice presidential running mates, but Reed has said he's not interested in the job. A top staffer to Delaware Sen. Joe Biden, another potential running mate, was also accompanying the group.

Lately, Obama's efforts to explain how he will use what he learns from U.S. commanders to refine his proposals have brought charges from Republicans and complaints from Democratic liberals that he seems to be shifting his Iraq policy toward the political center. But Obama maintains his basic goal of ending the U.S. combat role soon remains unchanged and that he's always said the U.S. withdrawal must be done carefully.

Obama also arranged to visit Jordan, Israel, Germany, France and England, traveling aboard a jet chartered by his presidential campaign, before his return to the United States. The weeklong trip marks his only foreign excursion as a presidential candidate; McCain has visited Canada, Colombia and Mexico, in part to highlight Obama's opposition to trade deals with those allies.

Few citizens in impoverished Afghanistan were aware of Obama's unannounced visit, and few have been following the U.S. presidential race, being too busy eking out an existence amid soaring violence and with limited access to news media.

But some interviewed Saturday said they would welcome an Obama presidency if he could help their country end the fighting, corruption and poverty that have crippled it for so long.

Click here to read more about al-Maliki's endorsement of Obama's troop withdrawal plan.

Click here to read more about Biden's staffer accompanying Obama.

Click here to watch video of Obama in Afghanistan.

The Associated Press contributed to this report.