The 1,897-kilometre pipeline would transport up to 830,000 barrels of crude a day from Alberta and Montana to facilities in Nebraska.
In doing so the administration overturned a ruling by then president Barack Obama in 2015 that denied a permit for the pipeline, largely on environmental grounds, in particular the USA contribution to climate change.
The pipeline was first proposed by Calgary-based TransCanada in 2008.
Judge Brian Morris granted an injunction to stop construction of the 1,900-kilometre pipeline, ruling that the U.S. State Department was obligated to "analyze new information relevant to the environmental impacts of its decision" to issue a permit for the pipeline a year ago.
"The Department instead simply discarded prior factual findings related to climate change to support its course reversal", Morris wrote.
Stephan Volker, an attorney for the complainants', called Morris' ruling "a landmark". New tar sands pipeline projects threaten Indigenous rights, put drinking water and communities at risk, accelerate the climate crisis and move us in the wrong direction.
The permit approval followed years of intense debate over the pipeline amid steadfast opposition from environmental groups.
Morris was appointed in 2013 by then-President Barack Obama, who had refused to grant a cross-border permit for the worldwide project.
Morris found that the U.S. government's use of a 2014 environmental review to justify issuing a presidential permit for construction of the cross-border pipeline violated the National Environmental Policy Act, the Endangered Species Act and the Administrative Procedure Act. His decision was one of scores of court rebukes to the Trump administration for decisions on the environment, immigration and transgender service in the military, among other issues, made hastily and, in the opinions of dozens of judges, without the "reasoned consideration" required by various federal laws, particularly the Administrative Procedure Act.
The fight over the project has spanned several presidencies and involved standoffs between protesters and law enforcement.
What is the Keystone XL Pipeline?
Also on Thursday, a federal appeals court ruled that President Trump can not immediately end the program, DACA, that shields from deportation young undocumented immigrants who were brought to the country as children.
He said the government's analysis did not fully study the cumulative effects of greenhouse gas emissions, the effects of current oil prices on the pipeline's viability or include updated modeling of potential oil spills.
The ruling is a major victory for environmentalist groups that sued to stop the project and for the Native American tribes that have protested against it for years.
Then came policy shifts in the Trump administration. He ordered the department to complete a full review. Construction of the United States leg had been scheduled to begin next year.
"An agency cannot simply disregard contrary or inconvenient factual determinations that it made in the past, any more than it can ignore inconvenient facts when it writes on a blank slate".