Columbia była pierwszym promem, który przeszedł zaplanowany program inspekcji i unowocześnień. W roku 1991 Columbia została przetransportowana do swojego „miejsca narodzin” – hali montażowej firmy Rockwell w Palmdale, Kalifornia. W pojeździe dokonano około pięćdziesięciu usprawnień, między innymi dodano karbonowe hamulce, poprawiono sterowanie koła dziobowego, usunięto instrumenty używane w fazie testowej orbitera, a także poprawiono system ochrony termicznej. Orbiter powrócił na Florydę w lutym 1992.
W roku 1994 Columbia została przetransportowana do Palmdale na swój pierwszy remont kapitalny, zwany Okresem Serwisowym Orbitera (ang. Orbiter Maintenance Down Period – OMDP). Taki gruntowny remont trwa zazwyczaj rok lub dłużej, po którym w pełni sprawny pojazd jest gotowy do użytku.
Drugi OMDP Columbia przeszła w roku 1999, kiedy to inżynierowie dokonali ponad stu modyfikacji orbitera. Najbardziej znaczącą zmianą było wprowadzenie wielofunkcyjnego systemu paneli (ang. Multi-functional Electronic Display System – MEDS) – „szklanego kokpitu”. MEDS zastąpił tradycyjne wskaźniki i pokrętła na rzecz małych, skomputeryzowanych ekranów.