La prima partita valida per le qualificazioni ad un torneo internazionale fu disputata dalla Nazionale andorrana il 5 settembre 1998, e si concluse con una sconfitta per 1-3 contro l’Armenia nelle qualificazioni al Campionato europeo del 2000, durante le quali Andorra perse tutte le dieci partite giocate, segnò 3 gol (di cui 2 su rigore) e ne subì 28; i migliori risultati furono le sconfitte casalinghe contro la Francia campione del mondo (0-1, con gol su rigore di Frank Lebœuf a cinque minuti dal termine) e contro la Russia (1-2), mentre la peggior sconfitta fu per 1-6 in trasferta di nuovo contro la Russia. Il 26 aprile 2000, in un’amichevole contro la Bielorussia, arrivò la prima vittoria della storia della Nazionale, per 2-0.
Nelle qualificazioni al Campionato mondiale del 2002 perse di nuovo tutte le dieci partite del proprio girone, in cui segnò 5 reti (record per la Nazionale nelle qualificazioni ad un torneo internazionale) e ne subì 36. I migliori risultati furono due sconfitte contro l’Estonia per 0-1 e 1-2 e una sconfitta contro Cipro per 2-3. La peggior sconfitta fu per 1-7 sul campo neutro di Lleida (Spagna) contro il Portogallo. Il 17 aprile 2002, in un’amichevole contro l’Albania, ottenne la sua seconda vittoria, con il risultato di 2-0. Nelle qualificazioni al Campionato europeo del 2004 perse tutte le otto partite del proprio raggruppamento, segnando una sola rete nella sconfitta esterna per 1-2 contro la Bulgaria e subendone 18. Nelle qualificazioni al Campionato mondiale del 2006 ottenne la sua prima vittoria in competizioni ufficiali: il 13 ottobre 2004 sconfisse 1-0 in casa la Macedonia del Nord, grazie ad un gol al 60º minuto di gioco del terzino dell’Elche (Seconda Divisione spagnola) Marc Bernaus, che girò in rete di destro un pallone recapitatogli al limite dell’area di rigore. Andorra riuscì a pareggiare altre due partite del girone per 0-0, contro la Macedonia e la Finlandia, concludendo con un totale di 4 reti fatte e 34 subite. Si tratta della campagna di qualificazione ad un torneo internazionale in cui Andorra ha raccolto più punti (5). Nelle qualificazioni al Campionato europeo del 2008 perse tutte le dodici partite del proprio raggruppamento, segnando due gol e subendone 42. Il risultato migliore fu la sconfitta casalinga per 0-1 contro la Russia, il peggiore la sconfitta esterna per 0-7 contro la Croazia.