The vote in New York this morning was carried by 138 votes to nine, with 41 countries, including Australia, abstaining.
The resolution lifts the Palestinian Authority's UN observer status from "entity" to "non-member state", the same status enjoyed by the Vatican.
Palestinians see the move as an important step in the peace process while the Israelis, supported by the United States, say it will only inflame tensions.
A major concern for the Americans is that the Palestinians could use their new status to join the International Criminal Court and pursue possible war crimes charges against Israel.
The US was swift to condemn the vote this morning, with secretary of state Hillary Clinton calling it "unfortunate and counterproductive".
However, Australian Foreign Affairs Minister Bob Carr said abstaining from the vote still sent a strong signal to Israel that they must negotiate.
He added the overwhelming support for the motion showed the world was growing impatient.
"[The vote was] a striking confirmation that world opinion is growing impatient and wants the two sides to negotiate a two-state solution, and as well, wants to offer the Palestinian people, the moderates in West Bank in particular, some promise and some hope," he said.
Senator Carr said Australia was comfortable to disagree with the US on the issue, but Washington was still the key to peace.
"It's an opportunity for America to reconnect, despite all the disappointments of the past, to getting those two sides together.
"In the end it's American goodwill and leadership that will deliver it and I'm convinced that President Obama wants to do this."
Pacific states say no
The Pacific Island states of Marshall Islands, Federated States of Micronesia, Nauru and Palau were among those to vote against the resolution.
Associate Professor Stephen Hoadley, an international relations expert from the University of Auckland, told Radio Australia the decision corresponded with dependence on the United States for economic support.
"The great deal of US aid and federal assistance, programs and so forth, continue to flow from the US mainland into these three Freely Associated States," he said.
Associate Professor Hoadley said the decision could also be linked to the fact that the Marshall Islands, the Federated States of Micronesia and Palau all had formal diplomatic ties with the Republic of China, Taiwan.
"It [Taiwan] is an entity which the United States continues to support very strongly even though the United States does not formally recognise it."
Palestinians 'believe in peace'
News of the vote sparked celebrations in Gaza and the West Bank, where the Palestinian Authority has its headquarters.
Earlier Palestinian president Mahmoud Abbas urged UN members to "issue a birth certificate" for a state of Palestine as he opened the debate in the General Assembly.
"Palestine comes today to the United Nations General Assembly at a time when it is still tending to its wounds and still burying its beloved martyrs of children, women and men, who have fallen victim to the latest Israeli aggression," Mr Abbas said, in reference to the recent Israeli assault on Gaza.
"Palestine comes today to the General Assembly because it believes in peace and because its people, as proven in past days, are in desperate need of it.
"Palestine comes today to this prestigious international forum, representative and protector of international legitimacy, reaffirming our conviction that the international community now stands before the last chance to save the two-state solution."
But the speech drew condemnation from the office of Israeli prime minister Benjamin Netanyahu, which issued a statement saying: "The world watched a defamatory and venomous speech that was full of mendacious propaganda against the IDF (Irael Defence Force) and the citizens of Israel."
Israel's ambassador Ron Prosor said the move to upgrade the Palestinians' status was "so one-sided it doesn't advance peace, it pushes it backward".
"As long as President Abbas prefers symbolism over reality, as long as he prefers to travel to New York for UN resolutions, rather than travel to Jerusalem for genuine dialogue, any hope of peace will be out of reach," he said.
Mr Prosor also tore into what he said was Mr Abbas's weakness, with the rival Hamas group ruling over Gaza, "40 per cent of the territory he claims to represent".
The US ambassador to the UN, Susan Rice, said the vote created "obstacles" to peace between the Palestinians and Israel.
"Today's unfortunate and counterproductive resolution places further obstacles in the path to peace. That is why the United States voted against it," she told the UN General Assembly.