Nadal, who will be 25 on Friday, the day of the semi-final, turned in easily his most impressive performance of the tournament, demolishing Robin Soderling 6-4, 6-1, 7-6 (7/3).
It was the Spaniard's second successive French Open win over Soderling after his victory in the 2010 final had avenged his stunning fourth-round defeat to the Swede the year before, still Nadal's only loss in Paris against 43 wins.
Murray charged into the semi-finals for the first time with a 7-6 (7/2), 7-5, 6-2 win over Argentinian veteran Juan Ignacio Chela.
He is just the second British player to reach the last four in Paris in the Open era (since 1968) after Tim Henman did so in 2004.
With Roger Federer and Novak Djokovic contesting the other semi-final, it will be the first time since the 2006 French Open that the top four seeds are into the last four in a grand slam event.
Despite being on the verge of losing his world number one spot to Djokovic, who he could yet meet in Sunday's title match, Nadal shook off the shackles which had restricted his performances in the earlier rounds.
Soderling, the 2009 and 2010 runner-up, was undone by 41 unforced errors.
"I played a very tough opponent. I'm happy I'm through to the semis," Nadal said.
"I was much better than in previous matches. I was more solid and Robin made more mistakes than usual."
Nadal was 3-0 up with a double break in the first set, the second of which was created by a sweet backhand pass, picked off his toes.
Soderling clawed back one of the breaks but Nadal, mixing breathtaking defence and accuracy from the back of court, got the best of a series of gruelling, rallies to take the 49-minute opener.
The big 26-year-old Swede was then broken three times in the second set with Nadal allowing him just three points on his own service while committing only two unforced errors.
Soderling was broken to trail 0-2 in the next game before he took advantage of a sloppy Nadal service game to retrieve the break.
That spurred him into a new lease of life as the set headed to the tie breaker.
Nadal went to three match points, courtesy of a sweeping forehand down-the-line winner, and took victory when Soderling netted a forehand.
Murray, who only completed his five-sets, fourth round win over Serbia's Victor Troicki 24 hours earlier, again started sluggishly, as he tested out the right ankle he injured against Michael Berrer in the fourth round.
"I was very up and down today. It was a scrappy match.
"I didn't start very well but got better and better. It wasn't a great level of tennis and I struggled with my rhythm."
The 31-year-old Chela, who had lost six straight times against the Scot, including in the last two years at Roland Garros, jumped out into a 4-1 lead with two breaks of serve before the fourth seed started to get into his stride.
The 24-year-old Murray saved two sets points to get to 5-4 and then on cue broke Chela's serve again to get level.
The set went to a tie-break which saw Chela win the first point against serve before Murray went on a run of five straight points to eventually take it 7/2 after which he headed off court for a comfort break.
On the resumption Murray grabbed another break and he looked totally in control as he smoothly moved 4-1 up with Chela looking for, but not finding, any answers to the Scot's domination.
Inexplicably, serving for the set at 5-2 up, Murray again seemed to lose his focus allowing Chela to win three games in a row, with two service breaks, to draw level at 5-5.
The Scot buckled down though to take the next two games for a two sets lead.
He then broke Chela yet again to start the third and this time he raced away to victory keeping alive his hopes of finally winning a grand slam title after three losing finals.
But to do so he will first have to get past Nadal who he has never beaten on clay.
- AFPTags: sport, tennis, france First posted June 2, 2011 05:46:00