Earlier, Biden was gushing with Netanyahu as he promised inseparable support of the U.S. to Israel.
Israel has announced the building of 1,600 new homes in east Jerusalem, in a move that threatens to overshadow US Vice-President Joe Biden's visit.
The move has angered Palestinians, whose leaders have only recently agreed to resume contacts with Israel - at Mr Biden's urging.
It is also likely to embarrass the Obama administration, given its timing.
The international community considers East Jerusalem, annexed by Israel in 1967, to be occupied territory.
Building on occupied land is illegal under international law, but Israel regards East Jerusalem as its territory.
Palestinian Authority spokesman Nabil Abu Rudeina told AFP news agency: "This is a dangerous decision and will hinder the negotiations.
"We consider the decision to build in East Jerusalem to be a judgment that the American efforts have failed before the negotiations have even begun."
Under US pressure, Israel has announced a 10-month suspension of new building in the West Bank. But the suspension excludes East Jerusalem, where the Palestinians want their capital.
There
are still various planning hurdles for the East Jerusalem project to
clear, and work is not thought likely to start for at least two years.
'Moment of opportunity'
Mr Biden is the most senior member of President Barack Obama's administration to visit Jerusalem.
Earlier, at a joint news conference with Israeli Prime Minister Benjamin Netanyahu, he said there was a "moment of real opportunity" for peace between the Palestinians and Israel.
Mr Biden welcomed the two sides' recent agreement to start indirect "proximity" talks, saying the US would back those who "took risks for peace".
Mr Biden said he hoped the indirect talks would lead to direct talks, through which a two-state solution with "Israel and Palestine side-by-side" could be reached.
The Palestinians refuse to hold face-to-face negotiations with the Israelis unless they halt all settlement building in the occupied West Bank, where the Palestinians want their future state.
US Middle East envoy George Mitchell is expected to shuttle between the Palestinians in Ramallah and the Israelis in Jerusalem.
Mr Biden also said the US was committed to Israeli security and determined to prevent Iran from acquiring nuclear weapons.
He added that the best long-term guarantee for Israel's security was a comprehensive peace between Israel and its neighbours.
Mr Netanyahu said Israel would continue to support the US push for stronger sanctions against Iran, and that he was pleased its efforts to restart Israeli-Palestinian peace talks were "beginning to bear fruit".
He said the goal of negotiations was a peace deal that included Palestinian recognition of the "permanence and legitimacy of the Jewish state of Israel".
West Bank building
Hours before Mr Biden's arrival on Monday, Israel enraged Palestinians by approving 112 new homes in Beitar Illit in the West Bank.
Israeli officials said the move was "an exception", and necessary to improve the settlement's security.
Palestinian leaders told Mr Mitchell that the move put the indirect talks at risk.
Close to 500,000 Jews live in more than 100 settlements built since Israel's 1967 occupation of the West Bank and East Jerusalem.
Correspondents say there is little optimism in the region about what the indirect Israeli-Palestinian talks might achieve.
Periods of direct negotiations over the last two decades have failed to reach agreement.
Mr Netanyahu's right-leaning government has taken a harder line stance on final status issues than that of the previous administration.
He has ruled out dividing Jerusalem, wants the Palestinians to recognise Israel as a Jewish state, and said he intends to maintain a presence along the eastern border of a future Palestinian state.
On Wednesday, Mr Biden will meet Palestinian leaders in the West Bank before travelling to Jordan for talks with King Abdullah.