The detainee's lawyer said on top of the jail time Brendan Thoms has done, and time in immigration detention, he now faces a third penalty of being torn from his tribal lands.
"What we say is that because Brendan is indigenous that the Constitution cannot treat him as an alien, that the power found in the Migration Act, cannot be used to deport him," Rod Hodgson of Maurice Blackburn lawyers in Brisbane told RNZ.
Brendan Thoms' mother Jenny is Aboriginal, his father an expat New Zealander who now holds Australian citizenship.
The family lived in New Zealand until Brendan was seven-years-old - he never obtained Australian citizenship since he's been there.
Thoms admitted he's made mistakes, reflecting on his 18-month sentence for domestic violence.
"It's nothing I'm proud of, I'm embarrassed about it," he said.
After serving his sentence, Thoms' visa was cancelled in September this year and he was put in a Brisbane detention centre.
"It's ridiculous, I honestly thought that I would be able to prove to them that I'm Aboriginal but their response to me was that they weren't even going to accept that when they were making a decision on the visa," Thoms told RNZ by phone from detention.
"It's ridiculous, I can't believe I'm in this situation," he said.
Thoms was asking to have an elder from his Gunggari tribe visit to get the word out to his people about his plight, but he said immigration officers had obstructed this.
"They basically said they can't organise it. Unlike in prison, there were no Aboriginal liaison officers to call on for help," he said.
"Y'know, I feel like my people done it hard, like my great-grandmother and my grandmother. I feel like I'm just hanging my head in shame walking around this place."
Thoms' cellmate recently agreed to be deported, even though it meant taking his Aboriginal children to New Zealand.
"They want to keep the family together, but they're taking the kids away from their land to do that - I was just heartbroken."
The man's tribespeople went to Federal Court, but the children's indigenous rights were not acknowledged, Thoms said.
Rod Hodgson has filed a writ in Australia's equivalent of the Supreme Court, aimed at making it illegal for the Federal Government to treat any Aboriginal as an "alien" as well as seeking damages for wrongful imprisonment.
It would be fair, in the meantime, for the immigration minister to use ministerial discretion to order Brendan Thoms' release, he said.
This recently happened with an Aboriginal man threatened with deportation to Papua New Guinea - he's mounting a similar legal challenge.
However, neither of these legal moves by Mr Hodgson will help detainees who have Aboriginal children but who are not themselves Aboriginal.
One such is Christian Tapaitau, a 38-year-old miner who by virtue of being born in Rarotonga is a New Zealand citizen, though he has never lived in this country.
He's vowing to resist deportation for the sake of his five children, aged 10 to 20.
"I don't wanna take them off their own land cos this is where they deserve to be. That's one thing I will never do is to take them from their own country, so I'm just going to keep fighting," Tapaitau told RNZ from the Brisbane detention centre.
He served eight months of a two-year sentence for assault and has been detained since August.
The immigration minister can overturn detention decisions and Rod Hodgson said the fathers of Aboriginal children could have a strong case.
Tapaitau still hopes to be home by Christmas, but his family is doing it hard, with his wife now driving a dump truck at a Queensland mine to make ends meet, and the authorities only make it worse, he said.
"I don't believe that the Government of Australia should be deporting Aboriginal people - this is their country, this is where they need to be."
Australia's Home Affairs Department which oversees immigration has not responded to a request for comment.
