The US president included Iran among "a small group of rogue regimes", and said the US would "totally destroy" North Korea if forced to do so.
Iran's foreign minister said: "Trump's ignorant hate speech belongs in medieval times", and not the UN.
North Korea has yet to respond to the president's threat of destruction.
Mr Trump's speech laid out a vision for a world filled with sovereign states which worked for the betterment of their citizens - but he spent large portions targeting what he called "rogue nations" which are "the scourge of our planet today".
Washington has repeatedly warned North Korea over its weapons tests, which violate UN Security Council resolutions.
On Tuesday, Mr Trump criticised North Korea's leader, Kim Jong-un, saying: "Rocket man is on a suicide mission."
"If [the US] is forced to defend itself or its allies, we will have no choice but to totally destroy North Korea," he added.
Reuters news agency said one audience member covered his face with his hands, and that loud, startled murmurs filled the hall in response.
Swedish Foreign Minister Margot Wallstrom, who was observed crossing her arms, told the BBC: "It was the wrong speech, at the wrong time, to the wrong audience."
The American leader called on "the righteous many" to confront "the wicked few".
In his speech, he called Iran "a corrupt dictatorship behind the false guise of a democracy" whose "chief exports are violence, bloodshed, and chaos".
He called the 2015 nuclear deal between Iran and world powers "one of the worst and most one-sided transactions the United States has ever entered into".
Mr Trump also targeted Venezuela, calling its government a corrupt "socialist dictatorship" - and warned that the US was prepared to take action against it.
Venezuela's Foreign Minister Jorge Arreaza rejected what he called "threats".
"Trump is not the president of the world... he can not even manage his own government," he said.
Bolivian President Evo Morales - an ally of the Venezuelan government - tweeted: "I am not surprised that a multi-millionaire like Trump attacks socialism. Our struggle will always be ideological and pragmatic."
French President Emmanuel Macron, also speaking to the General Assembly, defended the nuclear deal with Iran. "Renouncing it would be a grave error," he said.
But Israel's Prime Minister Benjamin Netanyahu backed Mr Trump during his speech, saying the deal with Iran should be amended or scrapped altogether, and warned against the spread of Iranian influence in the Middle East.
President Trump's speech was an eloquent exposition of his "America First" doctrine but at the same time contained some fulsome (and perhaps unexpected) praise for the United Nations as a body that can bring together sovereign states to tackle the world's problems.
In contrast to the focus on globalisation that has driven so much of foreign policy discussion since the 1990s, Mr Trump saw national sovereignty as the main pillar of the international system.
There was a nod to the old axis-of-evil theme. His rogues' gallery took in a predictable cast of North Korea, Iran and Venezuela.
Nonetheless Mr Trump's world view contained many contradictions. Where exactly is the boundary between national sovereignty and collective action? And does America's newfound foreign policy pragmatism extend just to calling for the return of democracy in Iran and Venezuela or actually for doing something practical about it?