Mr. Bush said he strongly disagreed with the decision - the third time the court has repudiated him on the detainees - and suggested he might seek yet another law to keep terror suspects locked up at the prison camp, even as his presidency winds down.
Justice Anthony Kennedy, writing for the 5-4 high court majority, acknowledged the terrorism threat the U.S. faces - the administration's justification for the detentions - but he declared, "The laws and Constitution are designed to survive, and remain in force, in extraordinary times."
In a blistering dissent, Justice Antonin Scalia said the decision "will make the war harder on us. It will almost certainly cause more Americans to be killed."
Mr. Bush has argued the detentions are needed to protect the nation in a time of unprecedented threats from al Qaeda and other foreign terrorist groups. The president, in Rome, said Thursday, "It was a deeply divided court, and I strongly agree with those who dissented." He said he would consider whether to seek new laws in light of the ruling "so we can safely say to the American people, 'We're doing everything we can to protect you.'"
Sen. Lindsay Graham, R-S.C., called the ruling a "dangerous decision" because in the middle of a war, military officers could be dragged into federal court, reports CBS News correspondent Wyatt Andrews.
"Never in the history or warfare have we allowed enemy prisoners to go to a federal court and sue our own troops to be released," Graham told Andrews.
Kennedy said federal judges could ultimately order some detainees to be released, but he also said such orders would depend on security concerns and other circumstances. The ruling itself won't result in any immediate releases.
The decision also cast doubt on the future of the military war crimes trials that 19 detainees, including Khalid Sheikh Mohammed and four other alleged Sept. 11 plotters, are facing so far. The Pentagon has said it plans to try as many as 80 men held at Guantanamo.
Lawyers for detainees differed over whether the ruling, unlike the first two, would lead to prompt hearings for those who have not been charged. Roughly 270 men remain at the prison at the U.S. naval base in Cuba. Most are classed as enemy combatants and held on suspicion of terrorism or links to al Qaeda and the Taliban.
"The lesson here, and it's a costly one for the administration, is that it can't try the terror suspects through Guantanamo Bay without creating procedures that the Supreme Court signs off upon - rules that give the men more rights than the White House has wanted to now for nearly seven years," CBS News chief legal analyst Andrew Cohen says.
Some detainee lawyers said hearings could take place within a few months. But James Cohen, a Fordham University law professor who has two clients at Guantanamo, predicted Mr. Bush would continue seeking ways to resist the ruling. "Nothing is going to happen between June 12 and Jan. 20," when the next president takes office, Cohen said.
Roughly 200 detainees have lawsuits on hold in federal court in Washington. Chief Judge Royce C. Lamberth said he would call a special meeting of federal judges to address how to handle the cases.
Detainees already facing trial are in a different category.
Justice Department spokesman Peter Carr said Thursday's decision should not affect war crimes trials. "Military commission trials will therefore continue to go forward," Carr said.
The lawyer for Salim Ahmed Hamdan, Osama bin Laden's one-time driver, said he will seek dismissal of the charges against Hamdan based on the new ruling. A military judge had already delayed the trial's start to await the high court ruling.
It was unclear whether a hearing at Guantanamo for Canadian Omar Khadr, charged with killing a U.S. Special Forces soldier in Afghanistan, would go forward next week as planned.
Charles Swift, the former Navy lawyer who used to represent Hamdan, said he believes the court removed any legal basis for keeping the Guantanamo facility open and that the military tribunals are "doomed."
Guantanamo generally and the tribunals were conceived on the idea that "constitutional protections wouldn't apply," Swift said. "The court said the Constitution applies. They're in big trouble."
Human rights groups and many Democratic members of Congress celebrated the ruling as affirming the nation's commitment to the rule of law. Several Republican lawmakers called it a decision that put foreign terrorists' rights above the safety of the American people.
The administration opened the detention facility at Guantanamo Bay shortly after the Sept. 11, 2001, terrorist attacks to hold enemy combatants, people suspected of ties to al Qaeda or the Taliban.
The prison has been harshly criticized at home and abroad for the detentions themselves and the aggressive interrogations that were conducted there.
At its heart, the 70-page ruling says that the detainees have the same rights as anyone else in custody in the United States to contest their detention before a judge. Kennedy also said the system the administration has put in place to classify detainees as enemy combatants and review those decisions is not an adequate substitute for the right to go before a civilian judge.
The administration had argued first that the detainees have no rights. But it also contended that the classification and review process was sufficient.
Chief Justice John Roberts, in his own dissent to Thursday's ruling, criticized the majority for striking down what he called "the most generous set of procedural protections ever afforded aliens detained by this country as enemy combatants."
Justices Samuel Alito and Clarence Thomas also dissented.
Justices Stephen Breyer, Ruth Bader Ginsburg, David Souter and John Paul Stevens - the court's more liberal members - joined Kennedy to form the majority.
Souter wrote a separate opinion in which he emphasized the length of the detentions.
"A second fact insufficiently appreciated by the dissents is the length of the disputed imprisonments; some of the prisoners represented here today having been locked up for six years," Souter said. "Hence the hollow ring when the dissenters suggest that the court is somehow precipitating the judiciary into reviewing claims that the military ... could handle within some reasonable period of time."
Scalia, citing a report by Senate Republicans, said at least 30 prisoners have returned to the battlefield following their release from Guantanamo.
The court has ruled twice previously that people held at Guantanamo without charges can go into civilian courts to ask that the government justify their continued detention. Each time, the administration and Congress, then controlled by Republicans, changed the law to try to close the courthouse doors to the detainees.
The court specifically struck down a provision of the Military Commissions Act of 2006 that denies Guantanamo detainees the right to file petitions of habeas corpus. Habeas corpus is a centuries-old legal principle, enshrined in the Constitution, that allows courts to determine whether a prisoner is being held illegally.
The head of the New York-based Center for Constitutional Rights, which represents dozens of prisoners at Guantanamo, welcomed the ruling.
"The Supreme Court has finally brought an end to one of our nation's most egregious injustices," said CCR Executive Director Vincent Warren. "By granting the writ of habeas corpus, the Supreme Court recognizes a rule of law established hundreds of years ago and essential to American jurisprudence since our nation's founding."
Mr. Bush has said he wants to close the facility once countries can be found to take the prisoners who are there.
Presidential candidates John McCain and Barack Obama also support shutting down the prison.