Hundreds of thousands of the stateless people - considered by the UN to be one of the most persecuted minorities on the planet - have left aboard rickety boats in past decades, and there are signs of another exodus looming.
"We are like dead people. I want to go to another country. I cannot keep suffering like this," said Rahima, 55, whose husband and 25-year-old son were killed in Buddhist-Muslim clashes in western Rakhine state in June.
"I don't have enough food. How long can I keep living here?" she told AFP in a recent interview, since which a fresh wave of violence has left dozens more dead and displaced about 30,000 people.
In the past Bangladesh was the destination of choice, but the neighbouring country has now closed its doors, turning away boatloads of Rohingya who attempted to flee the violence in June. Many have since hung their hopes on Muslim-majority Malaysia.
But for now, Rahima's home is one of the mud-strewn camps where tens of thousands of Rohingya have sought shelter since the conflict exploded in the flashpoint western region of the country formerly known as Burma.
They live in woeful conditions on the outskirts of the state capital Sittwe, crammed into tents, bamboo huts or simply living under tarpaulin sheets.
"There is hardship in the camps, and not enough food," said Mohammed Ismail, 32, his eyes welling up with tears. "After the rainy season, we want to leave."
He is not alone: with many others in the camps voicing a similar desire to flee, the United Nations and rights groups are bracing for a huge spike in "boat people" fleeing the country in the coming months.
"We are likely to see a dramatic increase in the number of Rohingya taking to the sea this year," said Matthew Smith, a researcher with New York-based Human Rights Watch.
"It's an incredibly risky endeavour for Rohingya refugees to take. It indicates the level of desperation that this population has experienced both in Burma and Bangladesh," he said.
Despite their decades-long presence, Myanmar views the roughly 800,000 Rohingya who are confined to Rakhine state as illegal immigrants from Bangladesh, and denies them citizenship.
Decades of travel restrictions, forced labour, land grabs and limited access to health and education services have already led many Rohingya to seek out a new life overseas.
Two massive waves of refugees, of approximately 250,000 people each, flooded across the border into Bangladesh in 1978 and 1991-92, but large scale repatriations ensued.
Now home to an estimated 300,000 Rohingya, Bangladesh refuses to accept more.
In desperation, the minority group has increasingly set its sights on getting to Malaysia, where there are now more than 20,000 officially registered Rohingya.
Between late 2011 and May this year, an estimated 7,000 to 8,000 Rohingya left Rakhine or Bangladesh by boat for Malaysia via Thailand, according to Chris Lewa, director of the Arakan Project, a Rohingya advocacy group.
It is a journey fraught with risk: in the past human rights activists have accused the Thai navy of pushing desperate Rohingya asylum-seekers back out to sea and casting them adrift.
Even so, boat departures by the Rohingya are at their highest level since the organisation began tracking the journeys five years ago, Lewa said.
This season the migrations, which can cost up to $2,000 per person, have started even before the end of the rainy season with "several hundred" Rohingya arriving in Malaysia since the June unrest, Lewa said.
One of them is Nur Islam, 23, who left Sittwe a few weeks ago.
"I was on the boat for 15 days without any food," he recalled. "I thought I might die there."
Five of his fellow passengers did not survive the journey and their bodies were thrown overboard, he told AFP in Kuala Lumpur.
But for the young Muslim, staying in the country where he grew up was not an option.
"Because of the danger I just left," he said. "I will never go back. There is nothing there. Everything has been burned down."
The arrivals may not be welcomed with open arms by Muslim countries, despite the vocal concerns about their plight raised by the Organisation of Islamic Cooperation, the top Muslim world body.
"I don't expect Malaysia or OIC countries to welcome the Rohingya," said Sarnata Reynolds from Refugees International.
"They may be kind in their response to the first few thousand, but the government and the residents will likely quickly grow weary and fearful of a mass exodus."
Yet for many Rohingya, the chance of a new life overseas is worth the risk.
"There is nothing to do here, so it's natural to try to find something better," said Kyaw Hla Aung, a Rohingya community leader in Sittwe. He hopes more of his people will be able to set off as soon as the weather permits.
But for the retired lawyer himself, who says he spent 14 years in jail for defending farmers' rights, the thought of leaving is too heart-wrenching.
"How can we abandon all the mosques downtown, how can we abandon our land?" he asked.
COMMENTS (2)
Comments are moderated and generally will be posted if they are on-topic and not abusive.
For more information, please see our Comments FAQ
"...how can we abandon our land?” he asked." But, he doesn't seem to understand that it is just not his land! It does not become your land because you claim it and build a mosque on it!