She will face top-seeded Maria Sharapova in Saturday's championship, the 19-year-old Russian advancing 6-4, 6-2 later Thursday over No. 4 Kim Clijsters in the second semifinal.
Williams and Sharapova are 2-2 in head-to-heads Williams winning their last encounter after saving match points in the semifinals here two years ago before going on to win the title.
Williams, a seven-time Grand Slam singles champion, weathered Vaidisova's powerful forehands and gave back plenty of her own, sometimes surprising the 17-year-old Czech player with her speed around the court and the pace of her ball.
After leading 5-1 in the second, she needed six match points before sealing it with an overhead.
"Yahooo!" she said, laughing and celebrating the win.
"She played some incredible points on match point," Williams said. "She just got relaxed. It reminded me a bit of myself. I just tried to stay focussed and tried to stay calm it was just great."
Sharapova overcame an early service break to dominate Clijsters, who was only able to convert two of her 12 breakpoint chances despite the Russian making eight double-faults and 33 unforced errors.
Sharapova, the U.S. Open champion, will be making her first appearance in an Australian Open final after two losses in the semifinals.
Clijsters, who will retire at the end of the season and plans to start a family, has lost four semifinals here and the 2004 final.
She gave Sharapova match point with a double-fault, and Sharapova clinched it with a forehand winner down the line.
Williams won two of her seven majors at Melbourne Park and is one win away from her most improbable title.
In between her win here in 2005 and her run to this year's final, Williams had not beaten at top 10 player and dropped out of the top 100 at one point last year.
By reaching the final, she is expected to surge back into the top 20.
"I can't believe it. That's awesome that was so fast," Williams said. "I'm excited. I have nothing to lose. I'm back in the top 20, that means so much to me."
Williams played only four tournaments in 2006, finishing the season 12-4 and without a title. She was the ninth-lowest ranked player to make a Grand Slam semifinal since computer rankings were introduced in 1975.
If she wins, she would be only the second unseeded player to win the Australian in the open era.
Vaidisova broke Williams' serve in the first game and was dictating early rallies until Williams broke back to level at 3-3.
The pair traded breaks late in the set, with Vaidisova going ahead 5-4 and having a set point on serve before Williams rallied to break back and force a tiebreaker.
The 25-year-old American led 5-1 in the tiebreaker but allowed Vaidisova back to 5-5, serving consecutive double-faults.
She set up set point with a backhand winner and let out a powerful "gggrrrr" after Vaidisova dumped a forehand into the net.
Williams broke Vaidisova twice and took a 5-1 lead in the second set but the No. 10 seed rallied and won four straight games, saving four match points after being down 0-40 to hold the ninth game, reports AP.
"I almost did a gagarooney there," said Williams, explaining: "Basically, you know gagging."
Serving again to finish it off, Williams had match point No. 5 at 40-30, when Vaidisova whipped a backhand crosscourt on the line for a winner.
Williams initially thought the ball was out and started to celebrate, then clearly wanted to challenge the decision but had no challenges left after using up her allotment earlier.
Her 10th ace of the match, on a second serve, set up Williams' sixth match point, and she finally cashed this one, throwing her hands in the air and leaning back to look at the sky.