By Jane Sutton

MIAMI (Reuters) - A U.S. appeals court on Tuesday overturned the convictions of five men found guilty of spying for Cuba and said pervasive prejudice against the government of President Fidel Castro had prevented them from getting a fair trial in Miami.

The U.S. 11th Circuit Court of Appeals in Atlanta ordered new trials for the "Cuban five," who were convicted in 2001 on conspiracy and espionage charges.

Three had been sentenced to life in prison and the others to 15- and 19-year terms, sentences that a United Nations human rights body condemned last month as arbitrary and unduly harsh for the men hailed in Cuba as national heroes.

The appeals court in Atlanta acknowledged in its ruling that reversing the convictions would be unpopular and offensive to many U.S. citizens.

"However the court is equally mindful that those same citizens cherish and support the freedoms they enjoy in this country that are unavailable to residents of Cuba," the court said. "One of our most sacred freedoms is the right to be tried fairly in a noncoercive atmosphere."

The five men were part of a ring that infiltrated U.S. military bases and Cuban exile groups and fed information to Havana, prosecutors said. The defendants said they caused no harm to the United States and gathered information solely to defend their homeland from attacks by Cuban exiles in America.

One defendant, Gerardo Hernandez, was convicted of conspiring to commit murder in a 1996 incident in which Cuban MiGs shot down two small planes flown by Cuban exiles over the Florida Straits. Four men died.

Hernandez admitted feeding information about the exile group to Havana but had no role in ordering the shootdown, his lawyer has said.

Defense attorneys argued that pervasive prejudice against Castro and the Cuban government and publicity surrounding the trial made it impossible for them to obtain a fair trial in Miami, which has a large Cuban exile population.

The trial began eight months after federal agents removed shipwreck survivor Elian Gonzalez from his Miami relatives, a heart-wrenching and divisive saga that received wide attention. The boy was returned to his father, who took him home to Cuba.

The jury that convicted the men did not include any Cuban Americans. But 16 of the 160 members of the jury pool knew the victims of the shootdown or knew trial witnesses who had flown with them.

Nearly all the jury candidates expressed negative views of Cuba and the only three who said they had mixed views of the island were dismissed, defense attorneys said.