The 41-year-old RadioShack Leopard rider moved ahead of the splintering pack in the final kilometre of stage three's uphill finish to claim a solo stage win on the short but punchy Mirador de Lobeira climb.
Horner, who is teamless for 2014, surpassed Pino Cerami and Andrea Noe's feats. Belgian Cerami was aged 41 years and 95 days when he won a stage at the 1963 Tour de France, while Noe led the Giro d'Italia in 2007 aged 38.
"I fully appreciate how important it is to win and lead a Grand Tour at my age, the older I get the more I value racing," Horner, who turned pro in 1995 but had never previously won a Grand Tour stage in his career, told reporters.
"Just take today, I could have crashed. At my age, that would have been my career over.
"I understand that every day I race could be my last day on the bike, but I love racing so much I want to continue."
Despite his age and a knee operation which prevented the former Tour of California from training for five months earlier this year, Horner said that he had been determined to be in top shape for the Vuelta.
A victory in the toughest stage of the Tour of Utah in August and second place overall confirmed the American was on track for the Spanish Grand Tour.
"We rode a strong team time trial here on Saturday and together with (team leader Fabian) Cancellara we agreed that the leader's jersey would be an objective for the team. That kept me very motivated and focussed for today," he said.
Horner leapfrogged overnight leader Vincenzo Nibali to the top of the standings after the Italian finished 11th on Monday.
The 2013 Giro d'Italia winner now trails Horner by three seconds, with Ireland's Nicolas Roche third.
"I am going to try for the overall victory, that's for sure," Horner said. "If I can win races like the Vuelta al País Vasco [in 2010], then why can't I win this one?"
"One guy was asking me today in the peloton if I knew of any director's jobs because he wants to retire soon. But I thought it was really bizarre, I mean - how can you want to stop racing?"
1 Christopher Horner (USA) RadioShack Leopard 4:30:18
2 Alejandro Valverde Belmonte (Spa) Movistar Team 0:00:03
3 Joaquim Rodriguez Oliver (Spa) Katusha
4 Rigoberto Uran Uran (Col) Sky Procycling
5 Daniel Martin (Irl) Garmin-Sharp
6 Bauke Mollema (Ned) Belkin Pro Cycling Team
7 Michele Scarponi (Ita) Lampre-Merida
8 Haimar Zubeldia Agirre (Spa) RadioShack Leopard 0:00:06
9 Nicolas Roche (Irl) Team Saxo-Tinkoff
10 Ivan Basso (Ita) Cannondale Pro Cycling
1 Christopher Horner (USA) RadioShack Leopard 9:37:40
2 Vincenzo Nibali (Ita) Astana Pro Team 0:00:08
3 Nicolas Roche (Irl) Team Saxo-Tinkoff 0:00:14
4 Haimar Zubeldia Agirre (Spa) RadioShack Leopard 0:00:16
5 Robert Kiserlovski (Cro) RadioShack Leopard 0:00:23
6 Alejandro Valverde Belmonte (Spa) Movistar Team 0:00:24
7 Rigoberto Uran Uran (Col) Sky Procycling 0:00:25
8 Rafal Majka (Pol) Team Saxo-Tinkoff 0:00:38
9 Roman Kreuziger (Cze) Team Saxo-Tinkoff 0:00:45
10 Leopold Konig (Cze) Team NetApp-Endura
- Sports & Recreation