The 24-year-old Nadal is now a brilliant 40-1 lifetime at Roland Garros and seeking his sixth title here in seven years. Only Bjorn Borg has won this event six times among the men in the Open Era (since 1968).
Up next for Nadal will be upstart Croat Antonio Veic, who knocked out 28th- seeded former top-five Russian star Nikolay Davydenko, 3-6, 6-2, 7-5, 3-6, 6-1.
The Australian Open finalist Murray had to work hard before advancing with a lackluster 7-6 (7-3), 6-4, 7-5 victory over Italian Simone Bolelli amid breezy conditions, while the fifth-seeded Soderling handled little-known Spaniard Albert Ramos 6-3, 6-4, 6-4 at the lone clay-court Grand Slam event.
Murray was the beneficiary of 58 unforced errors from Bolelli, compared to 35 miscues from the British winner, who piled up seven double faults and needed just over three hours to advance.
The Swedish Soderling cruised in just under two hours by allowing only one break of serve against the overmatched Ramos.
"A win in straight sets is always good," Soderling said.
Murray is a three-time Grand Slam runner-up who has never advanced beyond the quarterfinals at Roland Garros. He'll face German Michael Berrer on Saturday.
Soderling, who's a three-time titlist on the ATP circuit this season, lost to Nadal in last year's finale here and succumbed to Swiss icon Roger Federer in the 2009 championship match in Paris. Soderling, however, upset Federer in the quarterfinals here last year and shocked the mighty Nadal in the fourth round in 2009, giving Nadal his only loss at this prestigious event.
Soderling will face Argentine Leonardo Mayer in the round of 32.
One of last year's French semifinalists went by way of the upset here on Thursday, as eighth-seeded Austrian lefthander Jurgen Melzer was sent packing by unheralded Czech Lukas Rosol in five sets, 6-7 (4-7), 6-4, 4-6, 7-6 (7-3), 6-4.
The 25-year-old Rosol pulled off the upset in just under four hours on Court 2.
Tenth-seeded Mardy Fish, the highest-ranked American on the planet, moved on with a 7-6 (7-1), 6-2, 6-1 victory over Dutchman Robin Haase. This marks Fish's first-ever trip into the third round here.
Fifteenth-seeded Serb Viktor Troicki topped German Tobias Kamke 6-2, 6-2, 7-6 (7-4), while 16th-seeded Spaniard Fernando Verdasco got past Belgian Xavier Malisse 4-6, 6-3, 7-6 (7-5), 6-1, 18th-seeded former top-10 performer Gilles Simon overcame fellow Frenchman Jeremy Chardy 4-6, 6-4, 6-1, 6-4, and 21st- seeded Ukrainian Alexandr Dolgopolov spanked Austrian Andreas Haider-Maurer 6-2, 6-4, 6-2. The lefthanded Verdasco reached the fourth round in Paris the previous four years. Dolgopolov was a surprise Aussie Open quarterfinalist in January.
Mild upsets came when Colombian Alejandro Falla took out 20th-seeded German Florian Mayer 4-6, 7-6 (7-4), 6-1, 6-2; former world No. 3 Ivan Ljubicic of Croatia dropped 24th-seeded American Sam Querrey 7-6 (7-2), 6-4, 6-4 to reach the third round at Roland Garros for a sixth time; Leonardo Mayer drove out 27th-seeded Cypriot Marcos Baghdatis 7-5, 6-4, 7-6 (8-6); and Argentine veteran Juan Ignacio Chela outlasted 32nd-seeded South African Kevin Anderson 3-6, 6-3, 6-4, 4-6, 6-2. Querrey's loss leaves Fish as the lone American man still standing in Paris. Baghdatis is a former Aussie Open finalist.
Also on Day 5, Poland's Lukasz Kubot topped Argentine Carlos Berlocq 6-3, 7-6 (7-4), 6-3 and Berrer bested French veteran Arnaud Clement 7-6 (8-6), 3-6, 7-5, 6-4.
The third round will commence on Friday, including matches for second-seeded Aussie Open champ and U.S. Open runner-up Novak Djokovic and a third-seeded Federer.
Djokovic will look to improve to 40-0 this year when he faces 25th-seeded former world No. 4 Argentine slugger Juan Martin del Potro. The 24-year-old Djokovic and 22-year-old del Potro will do battle for a fourth time on the ATP World Tour, with the super Serb holding a 3-0 lifetime advantage.
The best-ever start to an ATP year was a 42-0 one by John McEnroe back in 1984. Djokovic would equal McEnroe with a trip into the semifinals here next week.
The 24-year-old Djokovic has actually won his last 41 matches overall, dating back to last season.
Djokovic already owns seven titles this season and would equal McEnroe and Ivan Lendl with a tour-record-tying eighth straight championship if he can secure his first-ever French Open title next week.
If Djokovic can reach the French finale, he would ascend to No. 1 for the first time in his career.
Djokovic has never reached the final here in Paris. He reached the final four here back in 2007 and 2008.
Federer will face 29th-seeded Serb Janko Tipsarevic on Day 6.
The 16-time major champion Federer titled here in 2009 to complete the career Grand Slam and was the runner-up to his great rival Nadal from 2006-08.
Seventh-seeded Spaniard David Ferrer will also take to the courts on Friday, as will seeded French favorites Gael Monfils, Richard Gasquet and Jo-Wilfried Tsonga.