The Columbia-HTC rider today crossed the finish line on stage three, 189km from Zutphen to Venlo, almost a bike length ahead of Slovenia's Borut Bozic. Spain's Oscar Freire was third.
The only previous victory by a New Zealand rider in the Tour of Spain's 73-year history was taken by Paul Jesson in 1980 in Santander.
The victory was Columbia-HTC's 13th stage win of the season in one of the major European professional cycling stage races and the New Zealander's first.
"I didn't know until five days ago I was going to be racing here, first I was on the list (for the Tour of Spain) and then I wasn't, I'm not sure why," Henderson told reporters.
"But I continued training hard and then when they (the management) realised they needed somebody to help (teammate Andre) Greipel in the finals, I made it back in and got really focused again."
After three days racing, the stage one winner Fabian Cancellara of Switzerland remains in the overall lead. Henderson is in second place, six seconds back and Germany's Gerald Ciolek, who won stage two, is third eight seconds down.
Henderson, 32, reflected on a day which is a career highlight since choosing to make road cycling the focus of his career.
He said victory almost came by accident, with top sprinters like Belgium's Tom Boonen of Quick Step and American Tyler Farrar of Garmin flummoxed by a chicane that dispersed the riders late in the stage.
"I was there in the last kilometre with Andre Greipel and Marcel Sieberg on my wheel," Henderson said.
"But there was a little chicane, some other riders came through very fast, and I followed them.
"When I looked back I couldn't see Greipel on my wheel, so I went for it myself. In yesterday's buildup for a bunch sprint, we were going well but there was a headwind, we lost some riders and we had to mix it in again."
"But we practise our leadout and when we get it right like today we're difficult to beat."
Among his previous standout wins on the road Henderson includes stages on the Tour of Georgia and the Tour of Catalunya.
On the track, Henderson won a Commonwealth Games gold in the points race in 2002, and a world title in the scratch in 2004.
Four weeks ago Henderson celebrated the birth of his first child, daughter Charlie, to his Australian wife Katie Mactier, who is also a former world track champion.
After four days' racing in Belgium, Germany and the Netherlands, the tour returns to Spain on Wednesday.
The race finishes in Madrid on September 20.
