The surprise visit comes as U.S. officials have been voicing growing concern that the al Qaida terror network has regrouped and Taleban insurgents are preparing a major new offensive in Afghanistan.
Both militant forces are believed to be using Pakistan's isolated tribal regions to mount cross border raids against U.S.-led coalition and Afghan forces.
In a written statement, Pakistan President Pervez Musharraf's office said the U.S. vice president called for "concerted efforts" to counter the threat.
But Pakistan insists it is already doing everything it can to secure the border and help defeat the Taleban.
The statement, released shortly after Cheney left Pakistan Monday afternoon, said General Musharraf underlined that Pakistan, Afghanistan, U.S. and NATO forces all have to take "joint responsibility" for securing the region.
Pakistan's foreign minister, Khurshid Kasuri, also defended Islamabad's record on the war against terrorism during a press conference after Cheney's visit.
"Pakistan's commitment to the elimination of al Qaida has been recognized. Any intelligence lead that we get, we follow, that is where the success comes about, by cooperation."
The vice president made no public comments in Islamabad and flew directly to Afghanistan, where he met with U.S. military leaders.
The White House remains a staunch public defender of President Musharraf, who is a key U.S. ally in the war against terrorism.
But Mr. Cheney's visit comes as signs increase that Washington and its allies are losing patience.
On Monday The New York Times reported that President Bush is looking to send a tough new message to Pakistan to help spur greater action.
The Times said President Bush is expected to warn General Musharraf that a frustrated U.S. Congress could cut military aid to Pakistan unless his forces help improve regional security.
The Pentagon has announced plans to deploy an additional three-thousand troops to Afghanistan to help repel any possible Taleban offensive.
London also plans to send more troops to Afghanistan even as it withdraws many of its forces from Iraq.
The British foreign secretary, Margaret Beckett, was also in Islamabad Monday, where she underscored London's concerns over increase militant activity in the region.
There are already approximately 45 thousand foreign troops in Afghanistan, including more than 27 thousand U.S. forces and five thousand from Great Britain.
Last year was Afghanistan's deadliest since the U.S.-led coalition ousted the hard-line Islamist Taleban government in 2001. Most of the fighting in the past year occurred in Afghan provinces along the Pakistan border.