Apdzīvotā vieta izveidojusies 13. gadsimtā, bet vēstures avotos pirmoreiz minēta 1499. gadā, kad Lietuvas kņazs Aleksandrs Jagellons to dāvājis bajāram Kšištofam Kmitam. 17. gadsimtā Korostišivā uzbūvēta pils un baznīca, kā arī tilts pār Teterivas upi. 1779. gadā Korostišivai piešķirtas Magdeburgas tiesības un ģerbonis; 1783. gadā pilsētā bija 600 iedzīvotāji. 1795. gadā Korostišiva kļuva par pagasta centru. 1850. gados pie Korostišivas sāka izstrādāt granīta karjerus un sākotnēji lielākā daļa strādnieku bija itāļi. 1873. gadā uz šejieni no Kijivas pārcēla skolotāju semināriju, pie kura 1883. gadā atvēra meteoroloģisko staciju. 1938. gadā Korostišivai atjaunoja pilsētas tiesības. Mūsdienās pilsēta ir granīta ieguves un apstrādes centrs.