La nazionale colombiana nacque verso la fine degli anni trenta: in seguito alla fondazione di una federazione calcistica unica (che aveva posto fine alle divisioni degli anni Dieci e Venti), avvenuta nel 1924, i dirigenti si concentrarono in primo luogo su una competizione che riunisse le varie selezioni locali colombiane, ciascuna rappresentante un dipartimento. Anni dopo, nel luglio 1937, per partecipare a un torneo calcistico internazionale organizzato in occasione del 400º anniversario della fondazione della città di Cali, la Federazione formò una selezione che riuniva in sé i giocatori della varie rappresentative locali. Benché la stampa definisse questa squadra Selección (cioè Nazionale), il torneo di Cali non è considerato una competizione ufficiale tra Nazionali maggiori, poiché a rappresentare Cuba vi era la squadra di club del Centro Gallego e in generale non parteciparono le Nazionali “A” dei vari paesi.
Il debutto ufficiale della Colombia avvenne quindi il 10 febbraio 1938, durante la quarta edizione dei Giochi centramericani e caraibici tenutasi a Panama. Guidata dal tenente Alfonso Novoa, la Colombia scese in campo alle 9:45 di mattina nella città di Panama contro la Nazionale messicana, in una partita arbitrata dall’uruguaiano José Mirabal, che diresse tutte le gare di quel torneo; la prima formazione della Colombia fu: Escorcia; Lugo, Lara; Joliani, Herrera, Yepes; Marcos Mejía, Torres, Pastor, Meléndez, Rafael Mejía. A realizzare il primo gol della storia della Nazionale fu Rafael Mejía, che andò a segno al terzo minuto; la prima divisa era blu con una striscia centrale bianca, pantaloni e calzettoni bianchi. La prima vittoria assoluta giunse il 14 febbraio 1938 contro la nazionale di casa.
Al termine del torneo la Colombia chiuse al terzo posto, dietro a Messico e Costa Rica; proprio contro la Costa Rica si verificò un avvenimento insolito: dopo l’assegnazione di un calcio di rigore in favore della Costa Rica, il secondo della gara, i colombiani protestarono vivacemente, tanto che la polizia dovette intervenire, portando via due calciatori colombiani. I compagni proseguirono nelle rimostranze, e dovettero tutti lasciare il campo; con la Colombia fuori dal terreno di gioco, i costaricani tirarono il rigore, segnando: la partita poi terminò, venti minuti prima del tempo regolamentare. In seguito a questi fatti venne avanzata una protesta ufficiale al Comitato organizzatore dei Giochi da parte della delegazione colombiana, cui però non venne dato séguito.
La Nazionale colombiana tornò poi in campo nell’agosto del 1938, in occasione della prima edizione dei Giochi bolivariani, in programma a Bogotà: esordì con una sconfitta per 4-2 con il Perù, cui ne seguì un’altra contro l’Ecuador, Nazionale debuttante in una competizione ufficiale. La vittoria contro il Venezuela fu l’unica del torneo, che per la Colombia si concluse con un 4º posto su 5 squadre, in virtù dei due punti conquistati. All’ultima gara, tenutasi il 16 agosto 1938 con la Bolivia e finita 2-1 per i boliviani, seguì una pausa di circa 6 anni e mezzo in cui la Nazionale colombiana non giocò alcun incontro internazionale.
Dopo la lunga parentesi d’assenza dai campi da gioco, la Nazionale colombiana guidata dal nuovo CT Pedro Ricardo López riprese la sua partecipazione al Sudamericano, e viaggiò verso Lima per disputare il torneo del 1957. L’esordio vide una sconfitta per 8-2 contro l’Argentina; il 17 marzo la Colombia riuscì però, per la prima volta, a battere l’Uruguay, grazie al gol di Carlos Arango che fissò il risultato sull’1-0. Il 24 marzo la Colombia venne battuta dal Brasile per 9-0, subendo la più pesante sconfitta della sua storia. A concludere la competizione fu la vittoria per 4-1 sull’Ecuador, grazie alla quale la Colombia evitò gli ultimi due posti della classifica, terminando 5ª su 7 Nazionali. Nel giugno 1957 la Colombia affrontò il suo primo torneo di qualificazione ai Mondiali, le eliminatorie per Svezia 1958: debuttò con un pareggio per 1-1 con l’Uruguay a Bogotà. Quel pareggio si rivelò essere l’unica gara in cui la Colombia ottenne dei punti: seguirono infatti tre sconfitte che classificarono la Nazionale andina all’ultimo posto, dietro a Paraguay e Uruguay. Il 23 giugno 1957 la Colombia disputò la prima amichevole della sua storia, contro il Paraguay, perdendo per 2-1: prima d’allora, la Nazionale aveva giocato solo all’interno di competizioni ufficiali.
Dopo’ultima gara al Mondiale l’attività della Nazionale venne nuovamente sospesa per circa nove mesi. La Colombia tornò a partecipare a un Sudamericano nel 1963: l’ultima edizione cui aveva preso parte era stata quella del 1957. Presentando una formazione rimaneggiata solo in parte rispetto al Mondiale (la linea d’attacco era sostanzialmente la stessa), la Colombia perse la prima gara con l’Argentina per 4-2. La competizione si concluse con 5 sconfitte e un pareggio (ottenuto con il Perù il 24 marzo, 1-1), e l’ultimo posto in classifica. Nel settembre 1963 la nazionale disputò due amichevoli contro la Costa Rica, perdendo la prima e vincendo la seconda: questi due incontri chiusero il 1963 della Colombia, che ancora una volta rimase lontana dai campi per diverso tempo, fino al luglio 1965.
Nel 1983 sulla panchina della nazionale arrivò Gabriel Ochoa Uribe, pluridecorato allenatore di Millonarios, Independiente Santa Fe e América de Cali. Nelle qualificazioni al campionato del mondo 1986 la Colombia abbandonò la divisa color salmone e iniziò ad usare i colori della bandiera nazionale: maglietta gialla, calzoncini azzurri e calzettoni rossi. Il 1º novembre 1985 la Colombia, che avrebbe dovuto ospitare i mondiali dell’anno successivo ma non poté adempiere ai requisiti della FIFA, mancò l’accesso alla rassegna perdendo contro il Paraguay: costretta dall’aritmetica a vincere per 3-0, vinse per 2-1. Nel 1986 León Londoño Tamayo, presidente della FCF, decise di affidare la panchina della nazionale a Francisco Maturana, che fondò l’ossatura della squadra sui giocatori dell’Atlético Nacional.
Grazie a una nuova generazione di talenti, nonostante la mancanza della principale stella Radamel Falcao per infortunio, i colombiani, che giocavano una fase finale del mondiale dopo 16 anni, brillarono nella fase a gironi, ottenendo tre vittorie su tre nel proprio raggruppamento, contro Grecia (3-0), Costa d’Avorio (2-1) e Giappone (4-1), confermando dunque le aspettative della vigilia come possibile sorpresa del torneo. La Colombia eguagliò così il risultato del 1990, ma questa volta superando il girone a punteggio pieno. Nel successivo ottavo di finale la nazionale colombiana si impose per 2-0 sull’Uruguay con una doppietta di James Rodríguez, divenuto inoltre il capocannoniere della manifestazione, e giunse per la prima volta della sua storia ai quarti di finale della coppa del mondo, dove fu però eliminata dai padroni di casa del Brasile, vittoriosi con il risultato di 2-1.
Nella Coppa America 2015 la squadra deluse. Sconfitta dal Venezuela (1-0), batté il Brasile (1-0) e pareggiò a reti bianche contro il Perù, qualificandosi al turno seguente come una delle due migliori terze classificate nei tre gironi. Ai quarti di finale pareggiò senza reti contro l’Argentina, che la eliminò dopo i tiri di rigore (5-4). Jeison Murillo, autore del gol della vittoria contro il Brasile, fu nominato miglior giovane del torneo e inserito nell’undici ideale della Coppa America.
Nella Coppa America Centenario del 2016 esordì battendo per 2-0 i padroni di casa degli Stati Uniti, poi batté anche il Paraguay (2-1) e si qualificò così alla fase successiva, ma come seconda classificata nel proprio raggruppamento, dato che, profondamente stravolta nell’undici titolare, perse l’ultimo incontro del girone contro la Costa Rica (3-2). Al MetLife Stadium pareggiò a reti bianche contro il Perù e lo sconfisse per 4-2 ai rigori. In semifinale fu sconfitta per 2-0 ed eliminata dalla nazionale futura vincitrice del torneo, il Cile. La Colombia guadagnò il terzo posto battendo nella finale di consolazione gli Stati Uniti per 1-0, conseguendo il proprio migliore risultato in Coppa America dal 2001, quando aveva vinto il torneo.