But a push to add another - reconciliation - has provoked a big fight with the Prime Minister, as progressive inner Melbourne councils look to join the battle to change the date of Australia Day.

At least three other councils - Moreland, Darebin and Hepburn Shire - are debating whether to follow the lead of Yarra Council, which voted unanimously on Tuesday night to no longer recognise Australia Day or hold citizenship ceremonies on January 26.

Yarra's move prompted a furious political backlash. Malcolm Turnbull didn't like it, telling parliament the decision was "utterly out of step with Australian values".

The federal government later followed through on a threat to strip the council of its power to hold any citizenship ceremonies.

"They are seeking to take a day which unites Australia and turn it into one which divides us," Mr Turnbull said.

Australia Day marks the arrival of the first British ships in 1788. It has also become known as Invasion Day among many Indigenous Australians.

Premier Daniel Andrews said the decision by Yarra Council was unnecessary: "I think we get the balance right [on Australia Day]. We respect the traditional owners of our land, but we then get on in a really unified way," he told the ABC.

Victorian opposition leader Matthew Guy said the council wasn't focused on its real job. If Yarra Council didn't "pull its head in", he said, then they should be sacked.

Former prime minister Tony Abbott joined in, describing the vote as an outrageous attack on Australia Day by a "mad lefty council".

However, the move in Yarra may only embolden other councils to follow suit and join the campaign to change the date. Three other councils have debated similar motions or will soon.

Two of the councils - Moreland and Darebin - form part of Melbourne's inner suburbs, where the Greens have made inroads at all levels of government.

A third, Hepburn, covers Daylesford and Kyneton, an area some call "north Northcote".

Moreland mayor Samantha Ratnam, a Green, said the council (which governs Brunswick and Coburg) would be watching what happens in Yarra closely.

A recent Moreland motion to no longer hold citizenship ceremonies on Australia Day was voted down narrowly by one vote.

Cr Ratnam said while the Yarra motion went further than what was proposed in Moreland, it may provide a model for a future push.

"The conversation has really shifted, people are starting to acknowledge how much pain and suffering celebrating Australia Day causes to our Indigenous community," she said.

In Darebin, which takes in a strip of Melbourne's north stretching from Northcote up to Reservoir, locals are reportedly being surveyed on their views about Australia Day ceremonies.

Earlier this year, Hepburn passed a motion to review whether January 26 was appropriate for celebrating Australia Day.

All eyes will now be on Yarra and whether they stick with their decision.

The City of Fremantle backed down from its push to cancel Australia Day ceremonies this year after being warned they would be hit with the same sanction.

Prospective citizens inside Yarra boundaries will now be sent to ceremonies held by neighbouring councils, or hosted by the Department of Immigration and Border Protection.

Assistant Minister for Immigration and Border Protection Alex Hawke has repeatedly said he would not tolerate "Greens-dominated councils" using citizenship ceremonies to campaign for changing the date of Australia Day.

Yarra mayor Amanda Stone said she had not expected the federal government would follow through on its threat to ban the council from holding citizenship ceremonies.

She said she would have preferred that the minister pick up the phone.

"It's unnecessary and an overreaction," she said. "We asked for a discussion but he's chosen to act instead. It's a shame."

However, she stood by the decision, saying that there had been a lot of support.

"People feel it's a very brave move, it's overdue," she said.