Stephens's total time of Friday in 22 hours, 53 minutes and 52 seconds gave him his triumph by 32 seconds over Ukraine's Alexander Gonchenkov.
The fifth and final stage was won by the Netherlands' Maarten den Bakker who completed the 169-km stretch from Nueva Carteya to the ancient Moorish city of Granada in four hours, 22 minutes and 10 seconds.
Den Bakker was briefly overtaken by Georgia's Vassili Davidenko in the final stretch, but a last strong push allowed the Dutch agricultural engineer to win.
Stephens' Spanish team ONCE came in nine minutes later after maintaining perfect control of Stephens's overall position.
"My goal in the Andalusian race was nothing more than just winning a stage," said Stephens in surprise at his overall victory. "This is a very important triumph for me."
He did not manage a stage victory in the race but he was second in the second stage and took the overall lead a day later.