"In the past, the United States government stove-piped it, they had an Afghan policy and a Pakistan policy. We have to integrate the two and I hope the rest of the world will join us in that effort," he told the BBC.
Mr Holbrooke said Taleban sanctuaries in Pakistan's tribal areas along the Afghan border were the primary problem for Kabul.
He also said that the era of "neglect" of the region was over, promising more troops and resources.
In other news from Afghanistan:
• Eight police officers are killed and one wounded after Taleban fighters ambush their convoy in the Spin Boldak district of the southern province of Kandahar
• Nato says its forces killed senior Taleban commander Maulawi Hassan and nine associates in an operation in Helmand province on Saturday
• Senior Afghan militant Sirajuddin Haqqani tells Reuters news agency attempts by the Afghan government to open peace talks with insurgents are a trick to divide militants
"What we're looking for is a comprehensive strategy [for Afghanistan]," President Obama told the CBS programme 60 Minutes on Sunday.
Richard Holbrooke: "Neglect was what happened in the past - that era is over"
"Threre's got to be an exit strategy. There's got to be a sense that this is not a perpetual drift."
Mr Obama - who last month ordered the deployment of an additional 17,000 US troops to Afghanistan - acknowledged that military force alone would not be enough to achieve Washington's objectives, which included the defeat of Taleban and al-Qaeda militants.
He said an effective strategy could include building up economic capacity in Afghanistan and improving diplomatic ties with Pakistan and other regional players.
But Mr Obama stressed that Washington "can't lose sight of what our central mission is".
"Making sure that al-Qaeda cannot attack the US homeland and US interests and our allies. That's our number one priority."
He said the central task was the same as when US troops went into Afghanistan after the 11 September 2001 attacks.
According to the British-based Guardian newspaper, the White House review has proposed creating a new senior executive or prime ministerial role in Kabul to work alongside President Karzai and dilute some of his power.
"Karzai is not delivering," a diplomat with knowledge of the review told the newspaper.
"If we are going to support his government, it has to be run properly to ensure the levels of corruption decrease, not increase. The levels of corruption are frightening."
The BBC's Ian Pannell in Kabul says a spokesman for the Karzai government welcomed Washington's move to provide additional troops and resources as part of its review.
But the spokesman warned against "quick fixes" and said that the US call to focus more on the Pakistani side of the border was "at least seven years too late".
The spokesman also dismissed any move to plant a high-profile figure in the government to circumvent President Karzai, saying it was up to the Afghan people to decide on their own future.
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.