Lower courts had deemed the ban unconstitutional, but the US top court reversed the decision in a 5-4 conservative majority ruling.
At a White House meeting to discuss Mr Trump’s proposed border wall he lauded the decision as “a tremendous success”.
The court’s reversal is viewed as a victory for the Trump administration.
The ban prohibits most people from Iran, Libya, Somalia, Syria and Yemen from entering the US.
Mr Trump said the Supreme Court decision was a “great victory” for the nation and constitution.
“We have to be tough and we have to be safe and we have to be secure,” the Republican president said in Tuesday’s meeting with lawmakers.
“The ruling shows that all the attacks from the media and the Democrat politicians were wrong, and they turned out to be very wrong,” he added.
He added: “If you look at the European Union, they’re meeting right now to toughen up their immigration policies because they’ve been over-run, they’ve been over-run.
“And frankly, a lot of those countries are not the same places anymore.”
The travel ban, which the Supreme Court allowed to take effect in December, has been widely criticised by refugee and human rights groups.
Chief Justice John Roberts wrote the opinion, which said the travel ban was “squarely within the scope of Presidential authority”.
He also rejected arguments that the ban discriminated against Muslims.
“The Proclamation is expressly premised on legitimate purposes: preventing entry of nationals who cannot be adequately vetted and inducing other nations to improve their practices,” Chief Justice Roberts wrote. “The text says nothing about religion.”
Shortly after the Supreme Court released its decision, President Donald Trump shared the news from his Twitter account.
Justice Ruth Bader Ginsburg joined Justice Sonia Sotomayor in the dissenting opinion, which argues the court failed to uphold the religious liberty guaranteed by the First Amendment.
“It leaves undisturbed a policy first advertised openly and unequivocally as a ‘total and complete shutdown of Muslims entering the United States’ because the policy now masquerades behind a facade of national-security concerns,” Justice Sotomayor wrote.
The dissent also states that “a reasonable observer would conclude that [the ban] was motivated by anti-Muslim animus”.
What does this ruling mean?
The travel ban has been in place since December, when the Supreme Court ruled that it could go into full effect, pending legal challenges.
The ban prevents most immigrants, refugees and visa holders from five Muslim-majority countries – Iran, Libya, Somalia, Syria and Yemen – as well as North Korea and Venezuela from entering the US.
But the restrictions on North Korea and Venezuela were not part of the legal challenge.
The ban allows for waivers on a case-by-case basis, but applicants who cannot afford an attorney to go through the waiver process will likely be unable to immigrate to the US, immigration advocates say.
Justice Stephen Breyer noted in his dissenting opinion that the state department reported that only two waivers were approved out of 6,555 applicants during the first month of the travel ban.
The high court has been issuing a number of decisions this week, including a ruling against a California law that required clinics to inform women of the availability of abortions paid for by the state.
The Court ruled that the law violated the free speech rights of Christian facilities.
Third time’s a charm
Analysis by Anthony Zurcher, BBC News – at the scene
Despite the controversial nature of Donald Trump’s travel ban, there were more abortion rights activists outside the Supreme Court on Tuesday morning than immigration protesters.
Perhaps it’s because abortion has been a contentious legal battle for decades, while the president’s travel directive had been in effect, and out of the headlines, for months.
Attention in recent weeks has been on migrants coming across the southern US border, not visitors and prospective residents from countries like Libya, Iran, Yemen and Syria.
Nevertheless, this marks a significant victory for Mr Trump – and for presidential power to set immigration policy in general – albeit by the narrowest of margins.
The five court justices said they took the president’s order on its face, and separated it from his more bombastic anti-Muslim comments made on the presidential campaign trail and via Twitter.
The travel ban was implemented haphazardly at the start of the Trump administration and faced repeated setbacks from the US legal system. In the end, however, the president got his way – or at least enough of his way to claim success.
The third time turned out to be the charm.
What’s the reaction?
The White House issued a statement saying the ruling was “a tremendous victory for the American People and the Constitution”.
“In this era of worldwide terrorism and extremist movements bent on harming innocent civilians, we must properly vet those coming into our country.”
Immigration lawyer Cyrus Mehta told the BBC that the majority opinion “gave in to President Trump’s hate and bigotry and will be viewed as a blemish”.
He added that Congress could overrule the decision “so that a future president will not have a blank check to block the entire people of a nation – from babies to grandmothers – out of hate, fear or bigotry. That is our only hope for redemption as a nation”.
Attorney General Jeff Sessions said in a statement that the decision was “critical to ensuring the continued authority of President Trump – and all future presidents – to protect the American people”.
Omar Jadwat, director of the American Civil Liberties Union (ACLU) Immigrant Rights Project called the ruling one of the court’s “great failures”.
“We must make it crystal clear to our elected representatives: If you are not taking action to rescind and dismantle Trump’s Muslim ban, you are not upholding this country’s most basic principles of freedom and equality.”
What’s the context?
Mr Trump’s ban has seen several iterations. Iraq and Chad were banned in previous versions. Iraq was removed for having “a close co-operative relationship with the US” and Chad for having “sufficiently improved its practices”.
The administration said that the ban was the result of carefully considering national security interests, but critics argued it was fulfilling his campaign promise for “a total and complete shutdown of Muslims entering the United States”.
The state of Hawaii had challenged the ban and a federal judge blocked its implementation.
Critics have noted that major attacks such as the 9/11 New York attacks, the Boston marathon bombing and the Orlando nightclub attack were carried out by people from countries not on the list, such as Saudi Arabia, Egypt and Kyrgyzstan, or by US-born attackers.