Melbourne is by far the most tolerant major Australian city towards Muslims, with Sydney most likely to be hostile.
Yet across the nation Australians show barely any support for calls from far-right groups to officially discriminate and reject would-be migrants on the basis of religion or ethnicity.
The results from a sweeping new survey of national attitudes released on Thursday by Monash University also reveal startling findings about the final year of Tony Abbott's government - that stopping the boats saw Australians actually more strongly supporting multiculturalism. 
The survey identified broad support for multiculturalism in mainland capital cities, but with differences most pronounced in sentiment towards Muslims.
Only 16 per cent of Melburnians reported a negative view of Muslims, compared with 27 per cent in Sydney. The findings in Sydney are closely matched in Adelaide, Perth and Brisbane. Canberra is the only city close to Melbourne with 16.1 per cent negative.
A marked difference also emerges between the cities and country regions, especially in Victoria, where urban people are more likely to have positive attitudes to Muslims.
However, while national security concerns spiked after the rise of Islamic State in Iraq and Syria, feelings of prejudice and racism have actually dropped.
The public also firmed in support of government assistance to ethnic minorities to maintain their culture and traditions, a proposition rejected in 2007 by almost two-thirds of Australians.
This is despite Mr Abbott being heavily criticised for divisive debates around Muslim women wearing the burqa or halal food.
But faith in the federal government to "do the right thing by Australians" flat-lined under Mr Abbott, never really recovering from a sharp fall since 2009.
Australians also worried about a growing gap between rich and poor in the Abbott years.
The Monash survey Mapping Social Cohesion - conducted in most years since 2007 to identify long term social trends - contains some warning signs.
People from non-English speaking backgrounds remained twice as likely to report experience of discrimination, and Muslims more than twice as likely as Roman Catholics to feel discriminated against.
Monash University social researcher Andrew Markus said the findings showed Australians broadly supported the policy to turn back asylum seeker boats and this appeared to have strengthened public faith the immigration system.
"The fact that the Abbott government re-established control of the border, looks to have created more confidence in the integrity of population management," Professor Markus told Fairfax Media.
He said Australia's broad support for multiculturalism was highlighted by the relative lack of controversy over the plan to settle 12,000 Syrian refugees, compared with European angst over migration.
"In Europe, 'multiculturalism' means the formation of ghettos and divided societies. In Australia, multiculturalism means integration," Professor Markus said.
The vast majority of Australians believe immigration is making the country "stronger" - a feeling that is much stronger among Australians in their 20s compared to those in their 60s.
Younger Australians are also far more likely to support the use of temporary skilled workers (67 per cent) compared to older Australians (44 per cent).
Young adults are less concerned than their parents and grandparents about questions of national identity, with about two-thirds of older and middle-aged Australians in their 40s strongly agreeing with the "importance of maintaining the Australian way of life" - but only 39 per cent of young adults.
Santini Subramaniam, 22, said Australia's identity was "constantly evolving" and that, in her experience, it had embraced different cultures.
"The first thing that comes to mind is a form of mateship, unity we have with one another," she said when asked about Australia's way of life.
Miss Subramaniam migrated from Singapore a decade ago, and while initially feeling she didn't belong, she now attended Anzac day dawn services as well as volunteering at a multicultural youth centre.