The six men, who say they fled into Pakistan from Chinese persecution were handed over to American forces by Pakistani bounty hunters during the early days of President Bush's war on terrorism.
They were later cleared of charges of terrorism by the United States Supreme court, but were kept in captivity at Guantanamo Bay because no country would take them until Palau agreed to give them temporary refuge.
Sean Dorney reports from Palau that the six Uighurs are developing family ties with the Uighur community in Australia.
Presenter: Sean Dorney
Johnson Toribiong, President of Palau; Abdulghappar Abulrahman; Uighur Ex Guantanamo Bay Detainee; Ahmad Abdulahad, Uighur Ex Guantanamo Bay Detainee; English teacher; Uighur driver
DORNEY: Most Australians who go to Palau do so for the spectacular diving around Palau's hundreds and hundreds of scattered idyllic islets known as the Rock Islands.
But a three year old Australian Uighur girl, Khadecha, and her five year old sister, Sabeha, have come to Palau to claim a new father.
Their late father died in a drowning accident back in Australia. Their new step-father is Adham Nabi who spent eight years in Guantanamo Bay.
In recent weeks, though, he has married their mother, an Australian Uighur woman whose uncle brought her to Palau for the wedding. The six Uighurs who have been in Palau since November were keen to hear what the President of Palau, Johnson Toribiong, had told me in an interview a few days earlier.
PALAU PRESIDENT JOHNSON TORIBIONG: When they first arrived I think they felt for the first time after seven or eight years the enjoyment of individual freedom, physical freedom from physical confinement. They are free here but we don't have a Uighurs community here. And as you know being physically free is not enough. You must have social relationships. One just got married recently to a lady from Australia who's a Uighur. And others are trying to connect with other Uighurs from all over the world and I can understand that. I mean they lost seven years during the prime of their lives and they want to have families. And they yearn to go to a community where they can enjoy social relations with their own people.
DORNEY: Why would you like to go to Australia?
ABDULGHAPPAR: We need to go to Australia because Australia is a big country. If we go to Australia we feel we will be safe. And in Australia there are Muslims and a Uighur community. Palau is a very small country, no Uighurs. There are no Uighurs.
DORNEY: Abdulghappar Abulrahman says they fled their homeland into Pakistan because of oppression.
ABDULGHAPPAR: In Turkistan what happens, for example, last year there were more Uighurs killed. China militarists killed them.
AHMAD ABDULAHAD: You know about our country what happened right now. There are no human rights. Always the government are causing suffering to our people.
Ahmad Abdulahad tells me they got caught when the Chinese declared dissident Uighurs terrorists and for a while, the Americans agreed. He found the price on his head in Pakistan was five thousand US dollars.
AHMAD ABDULAHAD: Unfortunately, what happened was September 11 and they took us. But from 2003 to 2009 the American Government pronounced us innocent people but no country would accept us. And we spent eight years, almost eight years we spent in Guantanamo Bay.
PALAU PRESIDENT JOHNSON TORIBIONG : When the United States Special Envoy for President Obama arrived in Palau in May of 2009, the Special Envoy is named Ambassador Daniel Freed, he brought a request from President Obama asking for Palau to accept temporary resettlement of the Uighurs from Guantanamo Bay detention facility because they'd been declared non enemy combatants by the Federal Court but they cannot go to the United States.
DORNEY: When the Uighurs arrived in Palau, they spoke almost no English.
PALAU PRESIDENT JOHNSON TORIBIONG: So we enrolled them at our Palau Community College where they are taking crash courses in the English language.
[Walking down the stairs and driving to the Community College]
The Uighurs do their English language courses five days a week. Although there were no lessons this day they offered to take me to their classroom.
UIGHUR: This is our class up there.
DORNEY: Their translator who was hired from Australia for six months by the Americans has now left. They've been broken up into two groups and do three hours of lessons, one group in the morning and the other in the afternoon. And they like their English teacher although she does not speak any Uighur.
AHMAD ABDULAHAD: She's very kind to us.
AHMAD ABDULAHAD; She's a really good teacher.
DORNEY: The tropical rain prompts a question or two about Australia.
DORNEY: Well, some parts of Australia get very little rain. Other parts get quite a bit. But Australia is a very dry place.
UIGHUR: Some rivers?
DORNEY: A river runs through the middle of Brisbane. And Sydney is based on a harbour.
UIGHUR: Right now, over there, hot? Hot?
DORNEY: No, at the moment in Australia it's quite cold.
DORNEY: The Uighurs say they are innocent victims caught up in a power play between two super powers, China and America. China claims they should be sent back to China to face the law because they are members of a terrorist organisation something they flatly reject.
ABDULGHAPPAR: Not, not terrorists! We are simple people.
DORNEY: Should anyone in Australia be afraid?
DORNEY: Afraid of you?
ABDULGHAPPAR: (Breaks into a smile) No, we are simple people. Why, why this? In Palau everybody [waves and says] 'How are you? Good.'
AHMAD ABDULAHAD; We are peaceful people and we are not criminals.
AHMAD ABDULAHAD: In 2003 the U.S. Government announced we are free men. Not the enemy of Americans or any country. But the Chinese Government needed to put us in jail.
DORNEY: On a trip to the sea shore we hear of another problem they have in Palau.
UIGHUR DRIVER: No more meat, no more halal food, no more halal Muslim restaurant. Cannot eat food outside. For us, difficult.
DORNEY: And once we reach the jetty the subject of food comes up again.
ABDULGHAPPAR: Sheep. Every time we eat sheep. That's our custom. There are, in Palau, no more sheep.
ABDULGHAPPAR: No more sheep.
DORNEY: In Australia there are plenty of sheep.
PALAU PRESIDENT JOHNSON TORIBIONG : I hope Australia will accept them. I think they've been freed from the Guantanamo Bay detention facility. I think Palau is a stepping stone to a country where they can really be free. Not only free but to enjoy the freedom that we all enjoy to live in the free world, to marry, to have friends, to work, to socialise.
AHMAD ABDULAHAD: Some of us want to get married. And right now we're beginning our life like from a zero beginning. Beginning life. We don't have anything. We only have ourselves. And we want to begin our life, our new life.
DORNEY - The sea and the tropics are quite foreign to these Turkistani men from China's Xinjiang Uighur Autonomous Province who hope the future for them lies far away from here down in Australia. And there are two little Australian girls who want to take their new step-father home with them. This has been Sean Dorney reporting from Palau for Pacific Beat.