Первое упоминание о церкви датируется 1628 годом. В начале XVII века на этом месте находился комплекс из двух деревянных храмов: «зимнего», посвященного святым мученикам Флору и Лавру, который дал название Лавровской улице, и «летнего», посвященного Иоанну Златоусту. В костромской писцовой книге упоминается: «В Златоустенской улице в Кузнецах церковь ружная древяна клецки святых мученик Флора и Лавра, да место церковное Иоанна Златоуста». На момент составления книги, последний храм, вероятно, сгорел, оставив лишь «место церковное».

В XVII веке деревянный храм Иоанна Златоуста был восстановлен, а к середине XVIII века на его месте возвели пятиглавую каменную церковь, освященную в 1751 году.

Каменный Иоанно-Златоустовский и деревянный Флоро-Лавровский храмы стояли рядом около 40 лет. Каменный храм был «холодным», и зимой службы проводились в деревянной церкви Флора и Лавра. К концу XVIII века она обветшала, и к Иоанно-Златоустовскому храму пристроили два «теплых» придела и колокольню с запада. Эти приделы, увенчанные небольшими главками, увеличили число глав храма до семи и были освящены в 1791 году.

Весной 1922 года в рамках всероссийской экспроприации церковных ценностей из церкви Иоанна Златоуста изъяли более 117 кг серебряных изделий: оклады для икон, священные сосуды и лампады.

В том же году исторические кафедральные соборы в бывшем Костромском кремле перешли в руки обновленцев, а новым кафедральным собором стал храм святого пророка Божия Илии на Русинской, ныне Советской улице. Когда в ноябре 1929 года он был закрыт, кафедральным собором стал храм святителя Иоанна Златоуста.

В 1959 году в ограде храма был похоронен епископ Костромской Сергий Костин.

В 1964 году Костромской Кафедральный Собор был перенесен в церковь Воскресения Христова на Дебре, а Иоанно-Златоустовская церковь стала приписной. В правление Н.С. Хрущёва власти планировали её закрытие и снос. Статус самостоятельной приходской церкви она получила лишь в 1966 году.