[7] In 1994, he became Parliamentary Secretary to the Shadow Minister for Health and Chairman of the Senate Community Affairs References Committee.

When the Coalition government was elected in 1996, Herron was appointed as Minister for Aboriginal and Torres Strait Islander Affairs, until he was replaced by Philip Ruddock in a January 2001 ministerial reshuffle.

The Stolen Generation affair was soon parodied in a web-based game that invited users to virtually steal his ten children,[9] and in reply Herron threatened the producers of the game (Russ Weakley[10] and Peter Firminger)[11] with legal action in the Supreme Court of Queensland.

AffairsHerron was admonished by Electronic Frontiers Australia:[12] "In a free society, it is completely unacceptable for politicians to use threats of legal action to silence their critics," said EFA Board member, Dale Clapperton.

Herron had no further response or action regarding the legal threat; the affair remained a significant moment in his political career.

[14] On his return to Australia, Herron was appointed chairman of the Australian National Council on Drugs, and The Royal Brisbane and Women's Hospital Foundation.

[citation needed] In 1994, he worked as a volunteer doctor in Rwanda, where he saw the aftermath of some of the atrocities committed there, an experience that would lead him to push strongly for Australia's support for the creation of the International Criminal Court.