The 31-year-old Pavlyuchenkova, back from a debilitating knee injury that shelved her in 2022, was playing in Paris for the first time since her dream run to the final in 2021.
Muchova breaks new ground in Paris
Czech world No.43 reaches her maiden Roland-Garros semi-final
Muchova, enjoying a stellar campaign after dealing with a slew of injuries, including an ankle injury that forced her to retire from her third-round clash with Amanda Anisimova at Roland-Garros in 2022, has been a rising force on tour in 2023 - she entered Tuesday's showdown with a 21-7 record on the season.
It would be the 26-year-old Czech who kept the momentum rolling with a decisive 7-5, 6-2 victory over Pavlychenkova on Court Philippe-Chatrier on Tuesday, to reach a maiden Roland-Garros semi-final and second at the Grand Slams overall (also made 2021 Australian Open semis).
Story of the match
It started as a closely-contested baseline battle, with Muchova edging in front by a break but failing to stretch her lead as the world No.333 drew a temporary line in the terre battue, saving five break points to hold for 2-3 before levelling up at three-all in the next game with a break of her own.
Another trade of breaks came, bringing the pair to 5-all, before Muchova turned on the jets and reeled off eight of the final 10 points of the set to take a 7-5 lead at the 60-minute mark.
Muchova made it 16 of 20 points won as she cruised through the opening two games of set two, and the Czech would never look back.
Pavlyuchenkova struggled to win points on serve in the second set and Muchova saved the only break point she faced while serving for the match at 5-2. She would soon close out the contest in one hour and 38 minutes.
Execution was the key for Muchova, who was able to wear Pavlyuchenkova down from the baseline and connect on a far greater portion of her shots. She finished with 21 winners against 15 unforced errors while Pavluchenkova struggled to find her range and ended the match with just 16 winners against 29 unforced errors.
Muchova's stronger baseline game was backed by superb serving. She won 64 per cent (16 of 25) of her second-serve points and 70 per cent of her first-serve points, while Pavlyuchenkova won less than half of her service points and barely half of her first-serve offerings (25 of 48, for 52 per cent).
What the winner said
Muchova, on her journey to the quarter-finals: "I don't know what to say - it's been an incredible two weeks and I'm just glad I'm still in the competition."
Muchova, on getting through a trying opening set: "I didn't serve it out, and I'm glad that I was able to break her and then I played with the wind. It was a little bit windy, so it was very important and I'm glad that it happened that way."
Muchova, on a difficult draw that saw her face former semi-finalist Maria Sakkari in round one: "When I saw it, it was a little bit funny because we played her two years in a row. I knew it was going to be very tough and we played on the same court so it was like deja vu, but it was a great match - I'm happy with the way I played and how I have come through the tournament."