Supreme Court is due in April to hear arguments over the ban and issue a ruling by the end of June
he Richmond, Virginia-based 4th US Circuit Court of Appeals, on a 9-4 vote, became the second federal appeals court to rule against the ban, finding that the Republican president's own words demonstrated that bias against Muslims was the basis of the policy.
The US Supreme Court has allowed the ban, put in place by Trump by presidential proclamation in September, to go into effect while litigation challenging it continues.
The 4th Circuit ruling went further than the earlier decision by the San Francisco-based 9th US Circuit Court of Appeals, which found that the ban violated federal immigration law, but did not address whether it also violated the Constitution. The Supreme Court has already said it will consider both issues in deciding the legality of the ban in the coming months.
The justices are due in April to hear arguments over the ban and issue a ruling by the end of June.
"Examining official statements from President Trump and other executive branch officials, along with the proclamation itself, we conclude that the proclamation is unconstitutionally tainted with animus toward Islam," 4th Circuit Chief Judge Roger Gregory wrote in the ruling.
The travel ban challengers "offer undisputed evidence of such bias: the words of the president," Gregory wrote, noting Trump's "disparaging comments and tweets regarding Muslims".
As a candidate, Trump promised "a total and complete shutdown of Muslims entering the United States". The court also took note of the fact that Trump in November shared on Twitter anti-Muslim videos posted by a far-right British political figure.
When Trump took office, he slashed refugee admissions to 53,000 from 110,000, a number that was cut again to a maximum of 45,000 in fiscal year 2018.
Trump's policy, the third version of the ban that he has issued since taking office in January 2017, blocks entry into the United States of most people from Chad, Iran, Libya, Somalia, Syria and Yemen. Trump has said the policy is needed to protect the United States from terrorism by Muslim militants.
US Justice Department spokeswoman Kerri Kupec said the 4th Circuit ruling "does not alter the status quo, and we look forward to ultimate resolution of these issues by the Supreme Court".
"Nothing is more important to the president and the attorney general (Jeff Sessions) than the safety and security of all Americans," Kupec added. "The president's lawful order remains critical to accomplishing that goal."
In the main dissenting opinion, Judge Paul Niemeyer said the courts should be deferential to the president on national security matters. Niemeyer criticised the court's majority, saying his colleagues applied "a novel legal rule that provides for the use of campaign-trail statements to recast later official acts of the president".
Thursday's ruling upheld a Maryland-based district court judge's decision in a case brought by the American Civil Liberties Union (ACLU), which represents several advocacy groups, including the International Refugee Assistance Project.
"President Trump's third illegal attempt to denigrate and discriminate against Muslims through an immigration ban has failed in court yet again. It's no surprise," ACLU lawyer Cecillia Wang said.