The NAW Heavyweight Championship was created in 2004 as a part of New Age Wrestling. The first match was a triple threat match with Mike Manson obtaining victory. However, in his first title defence he lost the title to the Candyman in a title unification match also involving the ARPW Heavyweight championship that the Candyman held. This match took place in Adelaide - the only time the title changed hands outside of Victoria.
The title has been vacated on two separate occasions. The first was in 2006 when George Julio defeated the Candyman for the title, but because of the way he won it Commissioner Tony Vutnik stripped Julio of the title and suspended him for twelve months. A triple threat match was held to fill the vacancy, won by Iron Horse Morrison. This began a sixteen-month reign as champion - the longest in the title's history.
The second vacancy occurred in 2009, when the reigning champion Sheik El Zacqwi was deported from Australia to the Middle East for welfare fraud. This vacancy was filled when Chip and Terra Australis had a match that Chip was victorious in. A claim to a second title victory by Pitbull before this match has been questioned as it was not announced as such on the evening.
At the end of 2014, controversy struck when - harking back to the infamous Fingerpoke of Doom in WCW - F.O.X retained the title with a Punch of Doom against Josh Extreme. Both of them turned out to be members of EGO.