La 12 aprilie 1981, această navetă a efectuat primul său zbor (STS-1) de la Centrul Spațial Kennedy (Florida), dovedind astfel viabilitatea conceptului de navetă spațială reutilizabilă. Comandantul acestui prim zbor a fost John Young (un veteran al programelor Gemini și Apollo) și pilotul navetei a fost Robert Crippen, care a ieșit pentru prima oară în spațiu. Columbia s-a întors pe Pământ la 14 aprilie 1981, după ce a navigat în jurul planetei de 36 de ori.
Prima misiune operațională, cu un echipaj format din patru astronauți, a fost STS-5, care a fost lansată pe 11 noiembrie 1982.
În 1983, a avut loc cea de-a doua misiune operațională a Columbiei (STS-9), având la bord șase astronauți, printre care și primul astronaut de altă naționalitate decât cea americană, germanul Ulf Merbold. Naveta spațială s-a reîntors în spațiu pe 12 ianuarie 1986, o dată cu lansarea STS-61-C.
La 23 iulie 1999, a fost lansată misiunea STS-93, comandată de lt. col. Eileen Collins, prima femeie care a comandat o navetă spațială. Cu acest prilej, Columbia a lansat telescopul spațial Chandra.
Printre realizările navetei Columbia se numără recuperarea Satelitului LDEF (misiunea STS-32 în ianuarie 1990) și experimentele din cadrul Laboratorului Spațial pentru Științele Vieții (misiunea STS-40 în iunie 1991).
La 1 februarie 2003, după misiunea STS-107 de 15 zile, 22 de ore și 17 minute (lansată la 16 ianuarie 2003), în cursul căreia au fost realizate circa 80 de experimente științifice, naveta Columbia s-a dezintegrat, prăbușindu-se în flăcări deasupra statului Texas, cu 16 minute înainte să revină pe Terra. Acest zbor a reprezentat cea de-a 28-a misiune a navetei Columbia.
Echipajul navetei Columbia era format din șapte astronauți. Comandantul misiunii, Rick Husband, avea 45 de ani și era colonel în cadrul Forțelor Aeriene ale Statelor Unite (USAF). Husband avea la activ 235 de ore petrecute în spațiul cosmic. William C. McCool, pilotul misiunii, avea 41 de ani, era pilot de încercare și fusese pilot în aviația Marinei Statelor Unite. El se afla la prima misiune. Michael P. Anderson avea 43 de ani și era locotenent colonel în cadrul Forțelor Aeriene. Anderson a petrecut 211 de ore în spațiul extraatmosferic. În cadrul misiunii STS-107 era responsabil al programului științific de la bordul navetei Columbia. David M. Brown avea 46 de ani și era căpitan în cadrul Forțelor Aeriene Navale. Era la prima misiune spațială. În cadrul misiunii STS-107, Brown deținea funcția de medic al echipajului.
Kalpana Chawla avea 41 de ani și era specialistă în inginerie aerospațială. Chawla participase la misiunea STS-87, fiind responsabilă cu brațul mecanic al navetei. Acumulase 376 de ore în spațiul extraatmosferic. Laurel Blair Salton Clark avea 41 de ani și era căpitan în cadrul Forțelor Navale. Era la prima misiune spațială. Ilan Ramon avea 48 de ani și era colonel-pilot în Aviația Miltară Israeliană și se afla, de asemenea, la prima sa misiune spațială.
Concluziile Comisiei de Investigare a Accidentului navetei spațiale Columbia au expus atât probleme tehnice, cât și probleme organizatorice. Accidentul a dus la oprirea operațiunilor cu navete spațiale timp de doi ani, așa cum s-a întâmplat și după dezastrul Challenger. Construcția Stației Spațiale Internaționale a fost oprită, și, timp de 29 de luni, stația s-a bazat exclusiv pe Agenția Spațială Federală Rusă pentru reaprovizionare și pentru rotația echipajelor, până când zborurile navetelor spațiale americane s-au reluat cu misiunea STS-114.
