Zbog svog geografskog položaja, današnja teritorija Kolumbije bila je koridor za ljude između Mezoamerike, Kariba, Anda, i Amazonije. Najstariji arheološki nalazi sa lokaliteta Monsu i Pubenza datiraju od dvadeset hiljada godina pre nove ere
Deset hiljada godina pre nove ere današnju teritoriju Kolumbije su između ostalih nastanjivali domorodački narodi Muiska, Kimbaja, Tairona. Zajednice lovaca-sakupljača koje su živele kod današnje Bogote trgovale su međusobno kao i sa narodima koji su živeli u dolini reke Magdalena. Nekih hiljadu godina pre nove ere zajednice Ameroindijanaca su razvile politički sistem kasikazgâ sa piramidalnom strukturom moći, na čijem čelu je bio poglavica ili na jeziku domorodaca cacique.
Španski istraživači, predvođeni Rodrigom de Bastidasom, su istražili karipsku obalu 1500. godine. Vasko Nunjez de Balboa je 1508. započeo osvajanje teritorije u zalivu Uraba a 1513. je bio prvi Evropljanin koji je stigao do Pacifičkog okeana, kog je nazvao Mar del Sul tj. Južno more.Posledica dolaska Evropljana bila je povećana smrtnost među domorodačkim narodima od bolesti na koje nisu bili imuni, kao što su velike boginje, što je dovelo do njihovog značajnog smanjenja. U 16. veku Evropljani počinju da dovode robove iz Afrike.
Španci su se naselili duž severne obale današnje Kolumbije početkom 16. veka. Zbog bojazni da bi zemlja mogla opusteti, španska Kruna je prodala zemljište guvernerima, osvajačima i njihovim potomcima što je omogućilo stvaranje velikih gazdinstava i rudnika. Robovi su uvedeni kao radna snaga. Takođe, radi sprečavanja desetkovanja domorodačkog stanovništva stvoreni su rezervati. Obnavljanje stanovništva je postignuto omogućavanjem kolonizacije seljaka i njihovih porodica koje su došle iz Španije. Ovime je počelo kolonijalno razdoblje. Vicekraljevstvo Nova Granada je zvanično stvoreno 1717, da bi zatim bilo privremeno ukinuto, i konačno ponovo uspostavljeno 1739. godine. Glavni grad vicekraljevstva je bila Santa Fe de Bogota. Vicekraljevstvo Nova Granada je obuhvatalo i neke provincije koje su ranije bile pod upravom Vicekraljevstva Nova Španija i Vicekraljevstva Peru. Tako je Bogota postala jedan od glavnih administrativnih centara Španije u Novom svetu, zajedno sa Limom i Meksiko Sitijem, iako je bila u izvesnoj meri zaostala u odnosu na ova dva grada u privrednom i logističkom pogledu.
Od početka kolonizacije ovog područja bilo je nekoliko pobunjeničkih pokreta. Poslednji koji se zalagao za potpunu nezavisnost od Španije je oformljen 1810, čime je obezbeđena značajna podrška budućim vođama ustanka: Simonu Bolivaru i Fransisku de Paula Santanderu.Jedan pokret koji je osnovao Antonio Narinjo, protivnik španskog centralizma i predvodnik opozicije protiv vicekraljevstva, izborio se za nezavisnost Kartahene u novembru 1811. Uprkos uspesima ustanka, pojava dve različite ideološke struje među oslobodiocima (federalizam i centralizam) podstakla je unutrašnji sukob i pomogla Špancima da povrate teritoriju. Vicekraljevstvo je obnovljeno pod komandom Huana de Samana, čiji je režim kaznio ustanike. Odmazda je podstakla obnavljanje pobune pod vođstvom Simona Bolivara. On je konačno proglasio nezavisnost 1819. godine. Prošpanske snage su poražene 1822. na teritoriji današnje Kolumbije a 1823. na teritoriji Venecuele.Teritorija Vicekraljevstva Nova Granada je postala Republika Kolumbija, organizovana kao unija Ekvadora, Kolumbija i Venecuele (Panama je u to vreme bila sastavni deo Kolumbije). Kongres u Kukuti je 1821. usvojio ustav republike. Simon Bolivar je postao prvi predsednik Kolumbije a Fransisko de Paula Santander potpredsednik. Međutim, nova republika je bila nestabilna i prestala je da postoji nakon što su se otcepili Venecuela 1829. i Ekvador 1830. godine.