Mick Keelty, the Police Commissioner, proposed the idea, saying the technique involved using respected imams or people previously connected with organisations deemed militant to convert extremists to more moderate views.
Alexander Downer, the foreign minister, said that while "reprogramming isn't the phrase I would use", the idea would be considered as it had been implemented successfully in Europe, the Middle East and Indonesia.
"Those governments have made an attempt to persuade extremists and terrorists who have been held in prison to change their point of view and to understand that it's not the Islamic way to kill, it's not the Islamic way to murder," he told reporters.
"And in some cases that process has been successful. It's something that we will give thought to."
Keelty told ABC Television's Lateline programme on Wednesday that the process, which he likened to treatment for drug addicts, had been successful in countries such as Indonesia, Pakistan, Sri Lanka and Britain.
Indonesia's anti-terrorist squad now had Nasir bin Abbas, former Jamaah Islamiah (JI) commander working for them and re-educating arrested JI recruits, he said.
"It's somebody they would have otherwise looked up to as a natural leader, in terms of a terrorist, and they've turned him around and used him to convert the others," Keelty said.
Indonesia had convicted around 200 people of terrorist-related offences since the 2002 Bali bombings and something had to be done with those offenders before they could be released back into the community, he said.
"Two hundred people incarcerated presents a problem if they haven't been reformed by the time they come back out into the community."
Australian police have worked with their Indonesian counterparts in the investigation of JI bomb attacks against tourists on the resort island of Bali and against the Australian embassy in Jakarta.
Keelty said he had raised the idea with the government in Australia, where 24 Muslim men are facing terrorism charges, but it would require a major policy shift and had gone no further.
"Essentially, it would be a threshold question in terms of policy as to whether we would engage in something that forces people into some sort of de-programming or de-radicalisation," he said.
Terry O'Gorman, spokesman for the Australian Council for Civil Liberties, opposed the plan.
"These countries the police commissioner mentions are involved in torture," O'Gorman said.
"This de-programming is part of the same basket of procedures."
O'Gorman said there was no evidence to suggest that the practice, which he said was better described as brainwashing, was effective in deterring terrorism.
But Waleed Kadous, spokesman for the Australian Muslim Civil Rights Advocacy Network, said a voluntary scheme had merit.
"It's important to highlight that already many respected scholars in the Muslim community are informally deconstructing terrorism and condemning terrorism to their congregations already," Kadous said.
"If it's voluntary we have no objection to it, but the problem once you make it compulsory is it just won't work, because religious leaders who do so will be seen as instruments of the government and will lose credibility to those people."