Kristofora Kolumba otrā jūrasbrauciena laikā uz Ameriku 1499.gadā tika atklāti tagadējās Kolumbijas krasti. Braucienā piedalījās arī Alonso de Oheda (Alonso de Ojeda), kuru vēlāk 1509.gadā Spānijas karalis nosūtīja izpētīt un iekarot šo teritoriju.

Pirms spāņu ierašanās 15.gadsimtā, Kolumbijas teritoriju apdzīvoja trīs lielas indiāņu saimes: čibču kultūra, kas apdzīvoja valsts centrālās augstienes un vēsā klimata joslas Sjerra Nevada de Santa Marta; karību cilts, kas apdzīvoja Atlantijas okeāna piekrasti, un arvaki, kas apdzīvoja Amazones, Putumajo un Kaketi upju baseinu teritoriju. 
  
Amerikas iekarošanas laikā Spānijas karalis katram konkistadoram deva tiesības dibināt jaunas pilsētas un tās pārvaldīt, pievēršot vietējos indiāņus kristietībai un maksājot nodevas Spānijas karaļnamam. 1550.gadā šī jaunā valdība sāka jaunu posmu, ko sauc par Koloniju (Colonia). 

Kolumbija ģeogrāfiski atrodas bijušās Spānijas koloniālās impērijas centrā un no 16.līdz 19.gadsimtam bija visu raksturīgāko Dienvidamerikas ģeopolitisko, ekonomisko un sociālo procesu vidutājs. 

18.gadsimta otrajā pusē Amerikā sākās protests pret kolonizatoru uzspiesto sociālo, ekonomisko un politisko kārtību. Jaunās Granadas neatkarība sākās ar Comuneros en el Socorro revolūciju, kas bija aizsākums Simona Bolivara vadītajai atbrīvošanas kustībai. Jāatzīmē 1819.gada 7.augusts, kad notika Bojakas kauja, kas bija izšķirošā valsts neatkarības iegūšanai pilnībā. Turklāt Kolumbijas nācija neatkarības kaujās ieguldīja visvairāk visā Dienvidamerikas kontinentā, jo kolumbiešu karavīri cīnījās arī Venecuēlā, Ekvadorā un Peru, līdz beidzot 1810.gada 20.jūlijā tika iegūta neatkarība no Spānijas. 

1863.gadā tika dibinātas „Kolumbijas Savienotās Valstis”, kas pastāvēja līdz 1886.gadam, kad valsts ieguva tās patreizējo nosaukumu Kolumbijas Republika. Tomēr iekšējais teritoriālais dalījums saglabājās, kas reizēm bija iemesls asiņainu pilsoņu karu uzliesmojumiem. Neilgi pēc tam, kad valsts daudzmaz bija politiski nostabilizējusies, 20.gadsimta četrdesmito un piecdesmito gadu mijā to pārtrauca politiskās nestabilitātes periods ar asiņainu konfliktu, kas pazīstams kā La Violencia(„Vardarbība”). Tā iemesls galvenokārt bija augošās nesaskaņas starp partizāņu grupējumiem, kas īpaši uzliesmoja pēc populārā kolumbiešu politiķa Horhes Gaitana slepkavības 1948.gada 9.aprīlī, kuru vēlāk nosauca par Bogotazo (jo notika Bogotā), kas paņēma vismaz 180 tūkstošu kolumbiešu dzīvības. 

1991.gadā tika ratificēta jaunā Kolumbijas Republikas konstitūcija, kas aizvietoja 1886.gada dokumentu. Konstitūcijā iekļauti galvenie politiskie, etniskie, cilvēktiesību un dzimumu līdztiesību jautājumi, kas pamazām ir ieviesti praksē, lai gan vienmēr ir pastāvējusi nevienmērīga attīstība, apkārtējās vides atšķirības un dažādi citi šķēršļi.  

Pēdējo desmitgažu laikā valsts ir cietusi no ietekmīgā narkotiku biznesa un geriljas revolucionāro (piemēram, Kolumbijas revolucionārie bruņotie spēki) nemieru sekām, kā arī citiem asiņainiem konfliktiem. 

Deviņdesmito gadu beigās prezidents Andrés Pastrana ieviesa jaunu iniciatīvu, ko sauc par Kolumbijas plānu, ar mērķi izbeigt bruņotos konfliktus un izveidot spēcīgu pretnarkotiku stratēģiju. 

Alvaro Uribes (Álvaro Uribe) (Kolumbijas Republikas prezidents kopš 2002.gada) prezidentūras laikā ir panākts dažu drošības rādītāju uzlabošanās, piemēram, ir samazinājies cilvēku nolaupīšanu un slepkavību skaits. Šie faktori ir veicinājuši ekonomisko izaugsmi un tūrisma attīstību.