JOIN USVettel, 23, dominated the delayed 2011 season-opener ahead of Lewis Hamilton in a damaged McLaren and Renault's Vitaly Petrov who got a first podium finish in the sport for Russia.
Red Bull's best Australian result until Sunday was fourth place from David Coulthard in the team's debut season 2005. Vettel was stopped by a technical problem in leading position during last year's race.
Reliability had been the only Red Bull concern after Vettel had routed Hamilton in qualifying Saturday by almost eight tenth of a second.
"Fantastic race, really controlled. Excellent car, excellent stops," said the elated Vettel via team radio after taking the checkered flag at Albert park.
Ferrari had to settle for fourth place from Fernando Alonso in the first race since a bad team pit stop strategy cost the Spaniard the 2010 crown in the final race and gave it to Vettel.
Bolstered by the pole, the youngest F1 champion Vettel made no mistakes at the start and pulled away quickly from Hamilton, Mark Webber in the second Red Bull and Petrov, who moved up from sixth.
Michael Schumacher's race was ruined in a first-lap collision which damaged his Mercedes and eventually forced him to retire in the 23rd lap. Mercedes' agony was complete when Nico Rosberg had to quit as well after Williams veteran Rubens Barrichello crashed into him.
"That's racing. It's a shame we came here with very different expectations," said Schumacher.
The 2009 and 2010 race winner Jenson Button failed for a long time to get past Felipe Massa's Ferrari in a thrilling duel for fifth. When he finally did so, he had to cut a corner and received a drive through penalty because stewards ruled he hadn't been ahead of Massa heading into turn 11.
Vettel retained the lead from Hamilton and Webber after the first round of pit stops while Button had to work has way back up from 12th once he had served the penalty and then pitted on lap 20.
The 2008 champion Hamilton was later hampered by a partly broken front floor after going wide into the grass but was able to carry on.
While Vettel, Hamilton and Petrov got through the race with two stops on the new Pirelli tyres, Webber and Alonso came into the pits three times which added to the spice.
Webber rode out after his final stop which may have cost him third place at the home race as Alonso went ahead. But none of the two were able to hunt down Petrov as the Russian held on to third with one stop less.
Vettel took the checkered flag in 1 hour 29 minutes 30.259 for the 58-lap race over 307.574 kilometres, 22.2 seconds ahead of Hamilton. Alonso, Webber and Button completed the top six.
A one-minute silence was observed ahead of the race as a tribute to victims of recent natural disasters in Japan, New Zealand and Australia.
The F1 season was originally due to start March 13 in Bahrain, but that race was postponed due to political unrest in the country. The next race is the Chinese GP April 9.