Byen blir første gang nevnt i krønikene for året 1213, men historikerne tror den kan ha blitt grunnlagt av Jurij Dolgorukij mer enn et halvt århundre tidligere. I likhet med andre byer i Vladimir-Suzdal ble Kostroma plyndret av mongolene i 1238. Den var da et lite fyrstedømme under ledelse av fyrst Vasilij av Kostroma, en yngre bror av den berømte Aleksander Nevskij. Vasilij arvet storfyrsttittelen i 1271, men han forlot ikke byen for Vladimir, og hans etterkommere styrte Kostroma i ennå et halvt århundre, til byen ble kjøpt av Ivan I av Moskva.
Ettersom Kostroma var en av de nordligste byene i Storfyrstedømmet Moskva, fungerte den ofte som et retrettsted for storfyrstene når fiender beleiret Moskva, så som i 1382, 1408 og 1433. I 1375 ble byen plyndret av pirater fra Novgorod («usjkujniki»). Byens spektakulære vekst på 1500-tallet kan tilskrives etablering av handelsforbindelser med engelske og nederlandske handelsmenn (Det moskovittiske kompani) gjennom havnebyen Arkhangelsk ved Kvitsjøen.
Det var på denne tid at Boris Godunov gjenoppbygde Ipatiev- og Åpenbaringsklostrene i stein. Byggearbeidene ble avsluttet like før byen ble vitne til noen av de mest dramatiske hendelsene i Russlands urolige tider. Kostroma ble to ganger herjet av polakkene, og det måtte en seks måneder lang beleiring til for å få fjernet dem fra Ipatievklosteret. Den heltemodige bonden Ivan Susanin ble et symbol på byens motstand mot fremmede inntrengere, og flere monumenter over han kan ses i Kostroma i dag. Den fremtidige tsaren Mikael Romanov bodde også i klosteret. Det var her at en utsending fra Moskva tilbød han Russlands krone i 1612.
Romanov-tiden
Det er forståelig at Romanov-tsarene betraktet Kostroma som sitt spesielle protektorat. Ipatievklosteret ble besøkt av mange av dem, inkludert Nikolai II, den siste russiske tsar. Klosteret ble grunnlagt tidlig på 1300-tallet av en tatarfyrste, en av Godunov-familiens aner. Romanov-tsarene bygde om den storslåtte Treenighetskatedralen i 1652, og dens fresker og ikonostaser er særdeles vakre. Et trehus av Mikael Romanov er fremdeles bevart i klosteret. Flere gamle trebygninger er også blitt transportert til klosteret fra fjerne distrikter i Kostroma oblast.
I 1773 ble Kostroma ødelagt av en stor brann. Etter brannen ble byen gjenoppbygd etter en ny byplan, hvor gatene strålte ut fra et sentralt sted ved elva. Det sies at byplanen ble til ved at keiserinne Katarina slapp viften sin ned på bykartet, og ba arkitektene følge hennes design. Kostroma er et av de best bevarte eksemplene på 1700-tallets byplanlegging, og i byen finnes fortsatt elegante bygninger i en «provinsiell nyklassisistisk» stil. Blant disse guvernørpalasset, et brannvakttårn, en rotunde ved Volga, og et sentralt marked overbygd med bueganger, med en kirke for handelsmenn i midten.
Severdigheter og landemerker
Den femkuplede Åpenbaringskatedralen, bygget i 1559-65, var den første steinbygningen i byen. Dens middelalderfresker er senere blitt ødelagt i en brann. Katedralen huser byens mest dyrebare relikvie, et bysantinskikon fra 900-tallet kalt Vår Frue av St. Theodor (russisk: Федоровская Богоматерь – Fedorovskaja Bogomater). Det var med dette ikonet at Mikael Romanov ble velsignet av sin mor før han dro til Moskva for å kreve den russiske tronen. Det sies at like før den russiske revolusjon i 1917 ble ikonet så svart at bildet knapt var synlig. Dette ble tolket som et dårlig tegn for Romanovdynastiet.
Ipatievklosteret har overlevd stort sett intakt til i dag, med sine murer og tårn fra 1500-tallet, klokketårn, og katedralen fra 1600-tallet. Bortsett fra klostrene ble de fleste av byens kirker enten ombygd eller revet i sovjettiden.
Næringsliv
Byens hovedvirksomheter er tekstilindustri, lysindustri, bildeler, treforedling og jordbruksrettet virksomhet, som baserer seg på de lite industrielt utviklede landdistriktene i oblasten. En av Russlands viktigste mineralvannskilder ligger i Kostroma oblast. I Krasnoje-na-Volga, rundt 70 km unna, ligger et juvelerkombinat.
I 1983 begynte byggingen av et kjernekraftverk av RBMK-typen. Etter Tsjernobyl-katastrofen ble byggearbeidet stanset.