They are traditional Indonesian boats known as praus and they brought Muslim fishermen from the flourishing trading city of Makassar in search of trepang, or sea cucumbers.
Exactly when the Makassans first arrived is uncertain.
Some historians say it was in the 1750s, but radiocarbon dating of beeswax figures superimposed on the cave paintings suggests that it was much earlier - one of the figures appears to have been made before 1664, perhaps as early as the 1500s.
They apparently made annual trips to gather the sea cucumbers, which fetched a high price because of their important role in Chinese medicine and cuisine.
The Makasssans represent Australia's first attempt at international relations, according to anthropologist John Bradley from Melbourne's Monash University - and it was a success. "They traded together. It was fair - there was no racial judgement, no race policy," he says.
Quite a contrast to the British. Britain designated the country terra nullius - land belonging to no-one - and therefore colonised the country without a treaty or any recognition of the rights of indigenous people to their land.
Some Makassan cucumber traders stayed, married Aboriginal women and left a lasting religious and cultural legacy in Australia. Alongside the cave paintings and other Aboriginal art, Islamic beliefs influenced Aboriginal mythology.
"If you go to north-east Arnhem Land there is [a trace of Islam] in song, it is there in painting, it is there in dance, it is there in funeral rituals," says Bradley. "It is patently obvious that there are borrowed items. With linguistic analysis as well, you're hearing hymns to Allah, or at least certain prayers to Allah."
One example of this is a figure called Walitha'walitha, which is worshipped by a clan of the Yolngu people on Elcho Island, off the northern coast of Arnhem Land. The name derives from the Arabic phrase "Allah ta'ala", meaning "God, the exalted". Walitha'walitha is closely associated with funeral rituals, which can include other Islamic elements like facing west during prayers - roughly the direction of Mecca - and ritual prostration reminiscent of the Muslim sujood.
"I think it would be hugely oversimplifying to suggest that this figure is Allah as the 'one true God'," says Howard Morphy, an anthropologist at Australian National University. It's more the case of the Yolngu people adopting an Allah-like figure into their cosmology, he suggests.
The Makassan sea cucumber trade with Aboriginal and Torres Strait Islander peoples ended in 1906, killed off by heavy taxation and a government policy that restricted non-white commerce. More than a century later, the shared history between Aboriginal peoples and Makassans is still celebrated by Aboriginal communities in northern Australia as period of mutual trust and respect - in spite of some historical evidence that this wasn't always the case.
The last Makassan fishermanUsing Daeng Rangka was the first Makassan captain to buy a licence from the British to catch sea cucumbers, and the last to visit Australia.
In 1895, after his boat was wrecked, he made a 400 mile (644 km) trip in a canoe.
As well as a large family in Makassar, Using had three children with an Aboriginal woman.
Using, sometimes called Husein, is still remembered in songs and dances in Arnhem Land.
In 1988, a descendent of his recreated the trip from Indonesia to Australia in a traditional prau as part of the latter country's bicentennial celebrations.
Meanwhile, the forbidding deserts of central Australia gave rise to a separate Muslim influx.
In a quiet suburb of Alice Springs, a town of 26,000 people in the heart of central Australia, there sits an unlikely building: a mosque. Its minaret rises against the backdrop of the craggy rock and red dirt of the MacDonnell Ranges.
It is called the "Afghan Mosque", and for a reason. Between 1860 and 1930 up to 4,000 cameleers came to Australia, bringing their camels with them. Many were indeed from Afghanistan, but they also came from India and present-day Pakistan.
They played a key role in opening up the deserts, providing supplies to remote mission stations, and helping to lay crucial national infrastructure like the Overland Telegraph Line and the Ghan Railway line, which still runs today, crossing the Australian desert from north to south. "Ghan" derives from "Afghan", as the train's logo of a cameleer makes plain.
"My grandfather's father, he was a camel driver," says 62-year-old Raymond Satour. "They had their own camels, over 40 camels," he says. "On the camel train itself, that's when they met the Aboriginal people that were camping out in the bush, and they got connected then - that's how we are connected to Aboriginals."
Far from their homes on the sub-continent, Afghan cameleers built makeshift mosques throughout central Australia, and many intermarried with Aboriginal peoples.
The work of the Afghan cameleers dried up in the 1930s, when motorised vehicles began to remove the need for the animals. Today, the Afghan Mosque in Alice is mostly filled with first-generation immigrants from India, Pakistan and Afghanistan. But worshippers from the mosque regularly visit the homes of some of the Afghan-Aboriginal descendants, including that of Raymond Satour. "The brothers come and hold prayer ceremonies and teachings," he says. "We're learning, and it's helping us keep alive our connection to Islam and the old Afghans."
These historical contacts have an echo in the present day, as a steadily growing number of Aboriginal people convert to Islam. According to Australia's 2011 census, 1,140 people identify as Aboriginal Muslims. That's still less than 1% of the country's Aboriginal and Torres Strait Islander population - and it should be said that Aboriginals are also becoming born-again Christians - but it's still almost double the number of Aboriginal Muslims recorded in the 2001 census.
Anthony Mundine, a former two-time WBA super middleweight champion and an IBO middleweight champion boxer, is perhaps the most high-profile Aboriginal Muslim convert. He takes inspiration from the American Black Power movement, especially from civil rights activist Malcolm X, a former leader of the Nation of Islam.
"Malcolm's journey was unbelievable," agrees Justin Agale, who is of mixed Aboriginal and Torres Strait Islander descent and converted to Islam 15 years ago. "Here was a man who was interested in social justice and in furthering the cause of his people but he was also interested in his own spiritual journey to truth."
Agale is one of a number of Aboriginal people who, fairly or unfairly, have come to associate Christianity with the racism of colonial Australia.
"One of the things that the colonialists were very successful in Australia in doing was teaching the indigenous people that God hated us, and that we were unwanted children, that we were being punished for being savages," he says.
By contrast, he sees Islam as a "continuation" of his Aboriginal cultural beliefs. Agale's ancestors in the Torres Strait, the Meriam people, observed something they called Malo's Law, which he says was "in favour of oneness and harmony", and he sees parallels in Islam. "Islam - especially the Sufi tradition - has clear ideas of fitra and of tawhid, that each individual's nature is part of a greater whole, and that we should live in a balanced way within nature."
This sense of the compatibility of Aboriginal and Islamic beliefs is not uncommon, says Peta Stephenson, a sociologist at Victoria University. Shared practices include male circumcision, arranged or promised marriages and polygamy, and similar cultural attitudes like respect for land and resources, and respecting one's elders.
Find out moreListen to Janak Rogers' report on Islam in Australia in Heart and Soul on the BBC World Service
"When I found Islam it was the first time in my life that I felt like a human," he says. "Prior to that I had divided up into 'half this, quarter that'. You're never a complete, whole thing."
Mohammed rejects the criticism that has been levelled at him by some Aboriginal people that he turned his back on his traditional way of life. He believes Aboriginal culture was destroyed by colonialism.
"Where is my culture?" he asks. "That was cut off from me two generations ago. One of the attractive things about Islam for me was that I found something that was unbroken.
"Do you go for something that is going to take you out of the gutter and become a better husband and father and neighbour? Or do you search for something that you probably never had any hope of ever finding?"
Listen again to Islam and Australian Aborigines on iPlayer or get the Heart and Soul podcast.
Follow @BBCNewsMagazine on Twitter and on Facebook