The visits came days after the U.S. announced it intention to adopt a new military strategy to better combat a growing Taliban and Al-Qaeda insurgency in both countries.
Gates held meetings with Afghan President Hamid Karzai and pledged U.S. support for Afghan plans to increase the size of the Afghan Army to 134,000 troops.
He said that by early next year, some 25,000 additional U.S.-led and NATO coalition troops will have been added since 2006.
There are currently some 33,000 U.S. troops in Afghanistan. But General David McKiernan, the commander of international forces in Afghanistan, has requested 10,000 more troops to combat resurgent Taliban and Al-Qaeda forces.
"The danger is that we'll be here longer and we'll expend more resources and experience more human suffering than if we had had more resources placed against this campaign sooner," McKiernan said.
'Security Just One Aspect'
Gates, however, highlighted other challenges of the mission in Afghanistan.
"As we all know, security is just one aspect of this campaign. Development and good governance are equally important," Gates said. "The international community is impressed by the goals set forth in the Afghan national-development strategy, as demonstrated at the June Paris support conference, when the United States and our partners pledged $21 billion in aid to the people of Afghanistan."
We are encouraged by the Pakistani military actions in the border area within the last several weeks.
Though Gates described the "aggressive actions by the Taliban coming across the border" as a major reason for the spike in violence inside Afghanistan, he refrained from directly criticizing Pakistan and emphasized the need for mutual cooperation.
"I think that the United States will work very hard to work with the Pakistani government to ensure that those who seek safe haven on the Pakistani side of the border are no longer allowed to operate with impunity from there," he said. "As I said earlier, we are encouraged by the Pakistani military actions in the border area within the last several weeks."
Gates also expressed regret to Karzai over recent civilian casualties in U.S. bombings and vowed that U.S. forces will do more to avoid future casualties. The number of civilians killed by U.S. and coalition military operations is on the rise.
"You have my word that we will do everything in our power to find new and better ways to target our common enemies while protecting the good people of Afghanistan," he said.
Speaking at the U.S. Embassy in Kabul, Gates offered his condolences to the families of the dead.
"While no military has ever done more to prevent civilian casualties, it is also clear that we have to work even harder," Gates said.
'Extremely Frank' Talks
While Gates was making these comments in Kabul, Admiral Mike Mullen, the chairman of the U.S. Joint Chiefs of Staff, was holding meetings with Prime Minister Yousuf Raza Gilani and the head of Pakistan's military, Ashfaq Pervez Kayani. The meetings follow several recent attacks by U.S. forces into Pakistan that have angered many officials in Pakistan.
In a statement, the U.S. Embassy in Islamabad said Mullen's talks were "extremely frank, positive, and constructive" and that he "reiterated the U.S. commitment to respect Pakistan's sovereignty and to develop further U.S.-Pakistani cooperation and coordination." He expressed appreciation for the "positive role" that Pakistan is playing in the war on terrorism and pledged U.S. support.
Earlier this month, Mullen said he was not convinced Western forces are winning the war in Afghanistan. He said he was "looking at a new, more comprehensive strategy" that would cover both sides of the border.
Mullen's comments came shortly before a U.S. missile strike killed five militants in northwest Pakistan. A Pakistani official quoted by Reuters said the attack on a container loaded with ammunition and explosives was the result of better U.S.-Pakistani intelligence sharing and that both countries had worked together on the attack.
Imtiaz Gul, an Islamabad-based journalist and analyst, told RFE/RL that Mullen's visit to Pakistan was prompted by recent comments by Kayani who said he had warned the U.S. against future ground attacks on Pakistan soil.
Pakistani leaders and public opinion was enraged by the September 3 ground raid by U.S. forces in Angoor Adda, a village in South Waziristan, near the Afghan border. That first documented U.S. raid reportedly killed 20 people, with each side disputing whether those killed were civilians or militants.
"General Kayani had tried to convey a message to the Americans that such ground operations would not be tolerated in the future," Gul says. "And after that, I think, a temper built [up inside Pakistan] against NATO, as well as American forces based in Afghanistan. And probably, Mike Mullen has come along with several other military men to calm down the tensions, the tempers here in Islamabad."
The U.S. magazine "Newsweek," however, reported last week that the U.S. and Pakistani militaries had reached a tacit understanding whereby U.S. troops will be allowed to conduct "hot pursuit" raids inside Pakistan, while Islamabad will be allowed to maintain complete deniability by publicly criticizing U.S. military actions.