Both have already won Wimbledon and the French Open and are bidding for their first Grand Slam title on a hard court.
Halep has been close before, losing the final in three sets at Melbourne Park to Caroline Wozniacki in 2018.
The 28-year-old Romanian said that tough loss was the main push for her breakthrough win that year at Roland Garros, where she beat Muguruza in the semifinals.
Halep needed only 53 minutes Wednesday to beat first-time major quarterfinalist Kontaveit 6-1, 6-1.
Muguruza took a little more than 1 1/2 hours to eliminated No. 30 Anastasia Pavlyuchenkova 7-5, 6-3, with both players struggling with their serves in the sun. The win earned Muruguza a spot in the semifinals at Melbourne Park for the first time, and her first at any Grand Slam tournament since the French Open in '18.
The loss dropped Pavlyuchenkova to 0-6 in quarterfinals at majors; she has entered 49 Slams without reaching the final four once.
There are three major winners in the last four, with reigning French Open champion Ash Barty playing No. 14 Sofia Kenin in the other women's semifinal Thursday. The top-ranked Barty is trying to end a drought for Australians at home: The last woman to win the singles championship was Chris O'Neil in 1978.
Halep spent her offseason away from home for the first time so she could focus fully on 2020 and her quest for a third major title.
"No days off," Halep said.
Kontaveit held the opening game at love. From then on, it was all one way as Halep went on a relentless, 11-game roll.
Halep worked for every point and only faced one break point, fending it off with a commanding forehand winner.
In the second set, Halep won the longest rally of the match — a 25-shot exchange — and then followed it up immediately with an ace on the way to 5-0 lead.
"I felt great today on court. I feel my game. I feel strong on my legs. I've been focused, every point," Halep said.
"This year I've started very well," she said. "I'm feeling much stronger than before."
Seeded fourth, Halep has advanced to the last four without dropping a set, and said she feels like she's playing her best tennis.
Top-ranked Rafael Nadal was scheduled to play his quarterfinal Wednesday night against fifth-seeded Dominic Thiem, the man he has beaten in the last two French Open finals. Stan Wawrinka, the 2014 Australian Open champion, was taking on seventh-seeded Alexander Zverev in an afternoon quarterfinal.