Freeing the men, the Lord Chief Justice said there was no proof of terrorist intent. The lawyer for one said they had been jailed for a "thought crime".
A jury convicted the students in 2007 after hearing the men, of Bradford and Ilford, east London, became obsessed with jihadi websites and literature.
The Home Office said it would study the judgement carefully.
It said it understood the Crown Prosecution Service was considering whether to appeal against the ruling, which it must do within seven days.
READ THE JUDGE'S RULING
Most computers will open this document automatically, but you may need Adobe Reader
It added that the threat of terrorism remained serious and real and the government was committed to ensuring it had the strongest possible anti-terrorism legal framework.
Irfan Raja, Awaab Iqbal, Aitzaz Zafar, Usman Malik and Akbar Butt were jailed for between two and three years each by the Old Bailey for downloading and sharing extremist terrorism-related material, in what was one of the first cases of its kind.
But at the Court of Appeal, Lord Phillips said that while the men had downloaded such material, he doubted if there was evidence this was in relation to planning terrorist acts.
He said the prosecution had attempted to use the law for a purpose for which it was not intended.
Lawyers for the men say the decision to restrict how the law on extremist literature works has huge implications for counter terrorism prosecutions.
Critics inside the Muslim community and civil liberty campaigners say section 57 of the 2000 Terrorism Act has been used as a blunt instrument to prosecute young Muslim men where there is no proof of genuine links to terrorism.
The BBC understands there have been three other convictions under this legislation - more cases are expected before the courts this year.
Imran Khan, solicitor for Mr Zafar, said the five had been prosecuted for "thought crime" and that the ruling would have an significant impact.
| It must go out to other young
people that it is a dangerous area, and
they have to keep themselves far, far away from visiting these websites
Dr Ghayasudin Siddiqui
He told BBC News: "Young Muslim men before this judgement could have been prosecuted simply for simply looking at any material on the basis that it might be connected in some way to terrorist purposes."
He said section 57 of the 2000 Terrorism Act had been written in such wide terms that "effectively, anybody could have been caught in it" but prosecutors would now have to prove such material was intended for terrorist purposes.
In a statement released through his solicitors, Mr Malik said he had always maintained his innocence.
"It is a great thing to live in a country where the Lord Chief Justice takes the time from hearing important cases to see if a group of unknown students have been fairly convicted for reading the wrong kind of literature," he said.
"As I said when I was arrested, I do not, have not and will not support terrorism in any form against innocent people.
"My prosecution was a test case under the 2000 Terrorism Act. Today's decision means no first year student can ever be prosecuted again under this Act for possessing extremist literature."
Mr Malik's solicitor, Saghir Hussein, said it was a "landmark judgement", with implications for other cases, including those alleging glorification of terrorism.
Akbar Butt said he was "just happy to be out". He told BBC News: "I'm thankful to be here and happy with the decision."
Zahid Iqbal, father of Awaab Iqbal, said he was feeling "great" after the decision.
"Justice has been done. It's restored my faith in the justice system," he said.
Asked if he had any advice for other young Muslim men who were looking at similar material, he said: "I don't think these boys did anything wrong. It was just propaganda they were looking at. They had no links to terrorism - everybody looks at websites."
'Knee-jerk terror laws'
Liberal Democrat home affairs spokesman Chris Huhne said the government's "knee-jerk drafting of new terrorism offences" had led to confusion on the part of prosecutors.
He said: "Ministers need to be more cautious when drafting new offences and more effective in enforcing old ones."
| Individuals who write poetry,
read blogs or download material from the
internet are being targeted because of their ethnicity or religious
Justice Secretary Jack Straw said it would not be appropriate for him to comment on the decision the Court of Appeal had made after "very careful consideration".
Muslim Parliament of Great Britain leader Dr Ghayasudin Siddiqui told BBC Radio 5 Live he welcomed the ruling but hoped that the students' experiences would serve as a warning to other young Muslims.
He said: "It must go out to other young people that it is a dangerous area and they have to keep themselves far, far away from visiting these websites."
Inayat Bunglawala, assistant secretary-general of the Muslim Council of Britain, said the Lord Chief Justice had been "right" to quash the convictions.
He said: "If there is no actual terror plot uncovered by the police then we do not believe we should be convicting people for what is effectively a thought crime."
The Islamic Human Rights Commission said it hoped Thursday's judgement would stop the "criminalisation of Muslim youth for downloading and reading material that is widely available to everyone".
Chairman Massoud Shadjareh said: "Our anti terror strategy should target and bring to account those who plan criminal acts of terrorism. Instead individuals who write poetry, read blogs or download material from the internet are being targeted because of their ethnicity or religious affiliation."