In his most sweeping decision since taking office a week ago, Trump, a Republican, put a four-month hold on allowing refugees into the United States and temporarily barred travelers from Syria and six other countries.
Civil rights and faith groups, activists and Democratic politicians were furious and vowed to fight the order.
Capping a day of confusion and chaos and protests in several airports across the country, a federal judge in Brooklyn, New York, granted a temporary reprieve. The American Civil Liberties Union successfully argued for a temporary stay that allowed detained travelers to stay in the United States.
Supporters outside the Brooklyn courtroom and at protests at airports in Dallas, Chicago, New York and elsewhere cheered the decision, but a bigger fight lay ahead.
The court action does not reverse Trump's order, which was criticized by some of America's closest allies.
Trump, a businessman who successfully tapped into American fears about terror attacks during his campaign, had promised what he called "extreme vetting" of immigrants and refugees from areas the White House said the U.S. Congress deemed to be high risk.
He told reporters in the White House's Oval Office on Saturday that his order was "not a Muslim ban" and said the measures were long overdue.
"It's working out very nicely. You see it at the airports, you see it all over," Trump said.
Along with Syria, the ban affects travelers with passports from Iran, Iraq, Libya, Somalia, Sudan, Syria and Yemen.
The Department of Homeland Security said about 375 travelers had been affected by the order, 109 of whom were in transit and were denied entry to the United States. Another 173 were stopped by airlines before boarding.
The new rules blindsided people in transit and families waiting for them, and caused havoc for businesses with employees holding passports from the targeted nations and colleges with international students.
Pegah Rahmani, 25, waited at Washington's Dulles airport for several hours for her grandparents, both Iranian citizens with U.S. green cards. "They weren't treating them very well," she said.
Rahmani's grandfather is 88 and legally blind. Her grandmother is 83 and recently had a stroke. They were released to loud cheers and cries.
'TIP OF THE SPEAR'
Several Democratic governors said they were examining whether they could launch legal challenges, and other groups eyed a constitutional challenge claiming religious discrimination.
"I don't think anyone is going to take this lying down," said Cleveland immigration lawyer David Leopold. "This is the tip of the spear and more litigation is coming."
The White House did not respond immediately to a request for comment. Senior officials at the U.S. Department of Homeland Security told reporters the government would implement any appropriate orders.
However, Mark Krikorian, the director of the conservative Center for Immigration Studies, called such lawsuits "last ditch efforts" that would only apply to a few individuals, and he said a broader constitutional argument would be hard to win.
"The first amendment doesn’t apply to foreigners living abroad. The law explicitly says the president can exclude any person or class of people he wants," Krikorian said.
Some leaders from the U.S. technology industry, a major employer of foreign workers, issued warnings to their staff and called the order immoral and un-American.
"This ban will impact many innocent people," said Travis Kalanick, chief executive of Uber Technologies Inc UBER.UL, who said he would raise the issue at a White House meeting on Friday.
Arab travelers in the Middle East and North Africa said the order was humiliating and discriminatory. Iran vowed to retaliate.
Sudan called the action "very unfortunate" after Washington lifted sanctions on the country just weeks ago for cooperation on combating terrorism. A Yemeni official expressed dismay at the ban.
Iraq's former ambassador to the United States, Lukman Faily, told Reuters that Trump's ban was unfair to a country that itself has been a victim of terror attacks, and could backfire.
"We have a strong partnership with U.S., more so in the urgent fight against terrorism. This ban move will not help, and people will start questioning the bond of this partnership, Faily said.
Allies in the United Kingdom, France and Germany were critical. Canadian Prime Minister Justin Trudeau tweeted a photo of himself welcoming Syrian refugees.
GREEN CARD CONFUSION
Confusion abounded at airports as immigration and customs officials struggled to interpret the new rules. Some legal residents with green cards who were in the air when the order was issued were detained at airports upon arrival.
However, senior administration officials said it would have been "reckless" to broadcast details of the order in advance.
Other officials said green card holders from the affected countries would require extra screening and would be cleared on a case-by-case basis.
Airlines were blindsided and some cabin crew were barred from entering the country.
Travelers were handled differently at different points of entry and immigration lawyers advised clients to change their destination to the more lenient airports, said Houston immigration lawyer Mana Yegani.
At Chicago O’Hare International Airport, brothers Bardia and Ayden Noohi waited for four hours for their father Kasra Noohi - who has an Iranian passport and a U.S. green card - to be allowed through.
They knew Trump had pledged tougher rules but did not expect the problems. "I didn’t think he’d actually do it," Bardia Noohi, 32, said. "A lot of politicians just talk."
Thousands of refugees seeking entry were thrown into limbo. Melanie Nezer of the Hebrew Immigrant Aid Society said she knew of roughly 2,000 who were booked to come to the United States next week.
Trump's order indefinitely bans refugees from Syria. In a television interview, he said he would seek to prioritize Christian refugees fleeing the war-torn country.
U.S. officials, speaking on condition of anonymity, said they were not consulted on the action and in some cases only learned the details as they were made public.
At the State Department, a senior official said lawyers were working to interpret the executive order, which allows entry to people affected by the order when it is in the "national interest."
However, a federal law enforcement official said: "It's unclear at this point what the threshold of national interest is."