Katusha's Rodriguez emerged from a battle with several top riders to cross the finish line, situated on the Green Mountain climb, in first place.
"It was a spectacular win ," said the Spaniard. "I'm very happy with this performance: my rivals are great riders, so the fact I managed to take this stage makes this victory even more important. Obviously they're not in top shape, but neither am I. I'm in good condition for February though.
"I knew this climb very well, because it is the third year I have taken part in the Tour of Oman. It is really demanding, but I knew where to start my sprint and this helped me a lot."
Froome finished in second - and with incumbent general classification leader Sagan (Cannondale) falling behind the front-runners, the Team Sky rider moved into the overall lead.
Cadel Evans (BMC Racing) finished third which puts the Australian second on GC, 24 seconds behind Froome. Alberto Contador's fourth-placed finish leaves him in third overall, an additional second behind Evans. Sagan's Cannondale stablemate Vincenzo Nibali came in fifth.
After 16km of the 144km stage Brent Bookwalter (BMC), Gregory Rast (RadioShack-Leopard), Gatis Smukulis (Katusha), Paul Voss (NetApp-Endura) and Matthias Friedman (Team Champion System) escaped.
They built up a lead of 4:10 as they crossed three gentle ascents but Saxo-Tinkoff, Astana and Katusha headed the peloton and the lead was less than two minutes with 14km remaining.
And they were caught early on the steep summit finish on Jabal Al Akhdhar, or “Green Mountain”, which tops out at 1235m where Purito beat a small but select group which did not include Tour de France winner Bradley Wiggins who was dropped on the lower slopes.
The Tour of Oman continues on Friday with the penultimate stage, a 144km trek from Al Alam Palace to the Ministry of Housing in Boshar - a stage which takes in three ascents of the brisk Bousher Alamrat climb.