La costruzione del Columbia iniziò nel 1975, a Palmdale (California). Venne chiamato così in onore della nave capitanata da Robert Gray che esplorò il Pacifico nord occidentale e divenne il primo vascello statunitense a circumnavigare il globo. Il nome Columbia, inoltre, ricorda il modulo di comando della missione Apollo 11. Completata la costruzione l'orbiter venne portato al Kennedy Space Center il 25 marzo 1979.
Il 19 marzo 1981, prima del lancio inaugurale, due tecnici rimasero uccisi e quattro feriti durante un test a terra sull'orbiter.
Il primo volo del Columbia fu comandato da John Young (un veterano dello spazio proveniente dai programmi Gemini e Apollo) e pilotato da Robert Crippen, mai stato nello spazio in precedenza, ma appartenente all'equipaggio di supporto per missioni Skylab e Apollo-Sojuz. Il 12 aprile 1981 (43 anni fa) lo Shuttle Columbia inaugura il Programma Space Shuttle, con la missione STS-1. Dopo 2 giorni in orbita il Columbia atterra con successo.
Nel 1983, il Columbia venne lanciato per la prima missione operativa (STS-9) con 6 astronauti a bordo, incluso il primo non-americano a bordo di uno Shuttle, il Tedesco Ulf Merbold. Il 12 gennaio 1986 il Columbia decollò con il primo astronauta ispanico, Franklin Chang-Diaz. Il 5 marzo 1998 la NASA nominò il tenente colonnello Eileen Collins come comandante di una futura missione Columbia, missione che rese Collins la prima donna a comandare uno Space Shuttle.
Durante la sua ultima missione, il Columbia trasportava a bordo il primo astronauta israeliano, Ilan Ramon e la prima astronauta donna indiana, Kalpana Chawla. Gli altri membri dell'equipaggio erano Rick Husband (comandante), Willie McCool (pilota), Michael Anderson, Laurel Clark e David Brown.
La mattina del 1º febbraio 2003, il Columbia stava rientrando in atmosfera dopo una missione scientifica di 16 giorni. La NASA perse i contatti radio alle 9:00 (meridiano est degli Stati Uniti), appena pochi minuti prima dell'atterraggio programmato alle 9:16 nel Kennedy Space Center in Florida. Diverse riprese video mostrarono i resti del Columbia in fiamme nei cieli del Texas, a un'altitudine approssimativa di 63 km e a una velocità di circa 20.160 km/h (5,6 km/s).
