Avant son passage chez les professionnels, il remporte 52 victoires en cadet, junior et amateur (11 saisons au total) : 15 victoires en cadet, 27 en junior et 9 au cours de ses 4 années passées chez les amateurs. La majorité de ces victoires sont obtenues au sprint. En 1999, sa dernière année de junior, il est sacré Champion d'Espagne et il est sélectionné pour les Championnats du Monde de Vérone où il chute dès le premier tour de circuit et doit abandonner.
En 2000 il devient cycliste amateur au sein de l'équipe Saunier Duval-Mapei. Il remporte deux étape du Tour d'Alava et l'année suivante, il se classe second au général du Lehendakari Txapelketa. En 2002, il rejoint l'équipe Olarra-Consultec dirigée par Xavier Artetxe. C'est probablement sa pire saison. Il reste au sein de cette équipe devenue Orbea-Olarra-Consultec jusqu'à son passage chez les professionnels, au sein de l'équipe Euskaltel-Euskadi.
Cyclisme professionnel
Saisons 2004 à 2006
Lors de ses trois premières saisons professionnelles, il n'obtient aucune victoire. Il décroche quelques places d'honneur comme la 2e place lors de la 3e étape du Tour du Limousin et de la 7e étape du Tour de l'Avenir, en 2004, ou la 3e place lors de la 3e étape du Tour de Pologne en 2006.
Saison 2007
En 2007, il s'impose au sprint lors de la 7e étape du Tirreno-Adriatico. Plus tard, lors du Tour d'Italie, il rencontre Mario Cipollini qui lui explique qu'il n'est pas assez musclé du haut du corps pour pouvoir faire sa place lors d'un sprint massif. Suivant les conseils du sprinter italien, Koldo Fernández va, pendant tout l'hiver, muscler le haut de son corps au gymnase.
Dès le début de saison, il remporte la 2e étape du Tour de l'Algarve. Une partie de l'équipe se mobilise pour l'emmener dans de bonnes conditions jusque dans les derniers mètres des étapes se terminant au sprint. Peu à peu, on constate des améliorations, mais il s'agit d'un travail de longue haleine qui tardera un peu avant de porter ses fruits. Lors de la classique Gand-Wevelgem, il prend la 6e place. Appelé à la dernière heure pour participer au Tour de France, il arrive hors-délais lors de la 8e étape. Le , il remporte le Circuit de Getxo et, le , il s'impose lors de la première étape du Tour de Burgos.
Fin de carrière
Déçu par ses résultats, le coureur espagnol annonce qu'il arrête le cyclisme après 11 saisons dans le peloton professionnel[1].
↑Alberto Contador, initialement deuxième de l'épreuve, a été déclassé en février 2012 par le tribunal arbitral du sport. Fernández, initialement troisième, est alors reclassé deuxième[2].