In 2000 Australia first competed in the qualification tournament held for the right to participate in the 2001 Division I championships. Australia lost all three of their group matches and finished seventh out of eight after beating South Africa in the seventh place game. The following year Australia again played in the qualification tournament in order to be promoted to Division I for the 2003 championships. Australia finished third in the group of five which saw Slovakia promoted to Division I for 2003.
In 2003 the International Ice Hockey Federation (IIHF) introduced a new format for the World Championships with the inclusion of second and third division. Australia was placed in the third division and gained promotion to the 2004 Division II tournament after winning four of their five games and finishing on top of the standings. The 2004 World Championships saw Australia relegated along with Great Britain from Division II to Division III for the 2005 tournament.
At the 2005 World Championships Australia competed in Division III and narrowly avoided relegation to Division IV after finishing fifth out of six teams, beating only South Africa. The next World Championship in 2007, Australia improved, again gaining promotion to Division II for the next years tournament. Promotion to Division II however was again short as Australia finished last in the 2007 tournament and were relegated back to Division III.