The German, still only 22 but heavily fancied for this year's Formula One title, lapped Albert Park's tight street circuit in one minute 23.919 under overcast skies for his second pole in two races.
While Red Bull lived up to their billing as the quickest cars on track, Lewis Hamilton's troubles continued.
The Briton qualified his McLaren only 11th, the morning after being booked by police and having his Mercedes impounded for "improper" driving after leaving the track.
"I wasn't fast enough. I feel I got everything out of the car, I just really didn't have any more grip out of the tyres," said the 25-year-old.
"So, (it's) unfortunate, but we'll still have a good race tomorrow hopefully."
Vettel, who finished fourth in the Bahrain season-opener after a spark plug failure robbed him of the lead, will be chasing Red Bull's fourth win in five races on Sunday.
"First of all it was a great result for both of us and the team," the German, who won four races last year and was runner-up in the championship, told reporters.
"I think that's a great achievement -- it's better than having two Ferraris up here."
SCHUMACHER HANDICAPPED
Despite setting the pace, Vettel said his fastest lap was a "getting a bit messy" toward the end."
"I lost it a little bit into (turn) 15, braking a bit late and I had a not so clean exit onto the main straight, so it wasn't ideal but still it was enough."
Webber, bidding to become his country's first home winner, was just over a tenth of a second slower than Vettel and felt disappointed after setting the early pace in the third session.
"Not really (happy), I would love to be on pole," said the Australian.
"It's a lot better than my qualifying in Bahrain ... In the end I did my best."
Ferrari's Fernando Alonso, winner on his debut for the Italian team in Bahrain, will line up third on the grid with McLaren's world champion Jenson Button alongside the Spaniard.
Michael Schumacher, the seven times world champion who made a comeback to F1 in Bahrain after a three-year absence, qualified seventh, one place behind Mercedes team mate Nico Rosberg.
The German great said he was satisfied but had been frustrated by other cars on the tight Albert Park circuit when pressing for a faster time.
"We had a reasonable qualifying session today and I am okay with the outcome, even if I was a bit handicapped by traffic, especially on my final quick lap," he said.
Alonso's Brazilian team mate Felipe Massa will start fifth on the grid on Sunday in Melbourne, where forecasts of late rain and strong winds may play havoc with tyre selection and strategy for the twilight race.
"Safety cars, accidents, it could be quite messy. So the main thing is to have a tidy race and bring the car home," Vettel added.
Lotus performed the best of the three new teams, but joined Virgin and Hispania (HRT) on the sidelines after both their drivers were knocked out after the first round of qualifying.
Australian Grand Prix qualifying result:
1. Sebastian Vettel (Germany) RedBull - Renault 1 min 23.919 secs
2. Mark Webber (Australia) RedBull - Renault 1:24.035
3. Fernando Alonso (Spain) Ferrari 1:24.111
4. Jenson Button (Britain) McLaren 1:24.675
5. Felipe Massa (Brazil) Ferrari 1:24.837
6. Nico Rosberg (Germany) Mercedes 1:24.884
7. Michael Schumacher (Germany) Mercedes 1:24.927
8. Rubens Barrichello (Brazil) Williams-Cosworth 1:25.217
9. Robert Kubica (Poland) Renault 1:25.372
10. Adrian Sutil (Germany) Force India-Mercedes 1:26.036
11. Lewis Hamilton (Britain) McLaren 1:25.184
12. Sebastien Buemi (Switzerland) Toro Rosso-Ferrari 1:25.638
13. Vitantonio Liuzzi (Italy) Force India-Mercedes 1:25.743
14. Pedro de la Rosa (Spain) BMW Sauber - Ferrari 1:25.747
15. Nico Huelkenberg (Germany) Williams - Cosworth 1:25.748
16. Kamui Kobayashi (Japan) BMW Sauber - Ferrari 1:25.777
17. Jaime Alguersuari (Spain) Toro Rosso - Ferrari 1:26.089
18. Vitaly Petrov (Russia) Renault 1:26.471
19. Heikki Kovalainen (Finland) Lotus - Cosworth 1:28.797
20. Jarno Trulli (Italy) Lotus - Cosworth 1:29.111
21. Timo Glock (Germany) Virgin - Cosworth 1:29.592
22. Lucas Di Grassi (Brazil) Virgin - Cosworth 1:30.185
23. Bruno Senna (Brazil) HRT - Cosworth 1:30.526
24. Karun Chandhok (India) HRT - Cosworth 1:30.613
Spotted: Nico Rosberg in Malaysia
Ferrari One-Two's ain't what they used to be
Alonso wins Bahrain GP on Ferrari debut
I would like to see Schumi beat Hamilton: Chandok
McLaren unveil supercar to tackle Ferrari in the auto market