Хотя костромские краеведы долгое время были убеждены, что кремль существовал на его нынешнем месте ещё во времена удельного княжества, археологическими исследованиями установлено, что город возник в устье реки Сула вверх по течению Волги. Деревянные укрепления города неоднократно горели и были подвержены нападениям новгородских ушкуйников, поэтому после очередного разорения в 1416 году кремль был перенесён на нынешнее возвышенное место. Вероятно, тогда же городской собор был переименован из Феодоровского в Успенский.
Первое каменное здание кремля и всего города, Успенский собор, датируется началом правления Ивана Грозного. В связи с особым почтением, которое новая династия Романовых оказывала хранившейся в соборе Феодоровской иконе Богоматери, он был в XVII веке расширен, с прибавлением обширного Феодоровского придела. Из росписи кремля 1678 года следует, что он был обнесён деревянной стеной с многочисленными башнями, Чудовой, Тайничной, Наугольной, Водяной, Вознесенской, Богословской, Ильинской, Воскресенской, Спасской и Пречистенской. Ближе к Волге стоял Здвиженский монастырь с шатровым храмом. В старинных описях также упоминается о существовании в кремле ещё двух церквей, Троицкой и Похвалы Богородицы.
Пожар 1773 года уничтожил Здвиженский монастырь и шатровую соборную колокольню. Успенский собор был поновлён, а на месте монастыря по проекту местного умельца С. А. Воротилова был возведён тёплый Богоявленский собор в стиле позднего барокко, с архиерейской усыпальницей в подклете. Строительные работы в кремле не затихали до 1791 года. Тогда же был устроен новый вход со стороны города, в виде вычурных по архитектурному решению Триумфальных ворот, и была возведена 64-метровая ярусная колокольня, главная архитектурная доминанта дореволюционной Костромы. Фортификационные сооружения Старого и Нового города разбирались, а рвы засыпались на протяжении XVIII—XIX веков. К настоящему времени сохранились лишь остатки восточного рукава вала Старого города и эскарпированные склоны верхней террасы Старого города. В 1922 году кремлёвские храмы были переданы обновленцам, в 1929 году закрыты, в 1934 году снесены. На месте храмового комплекса в историческом центре Костромы был разбит парк, центром которого стал исполинский памятник В. И. Ленину. Он был поставлен на пьедестал, подготовленный в 1913 году, во время празднования 300-летия династии, для грандиозного памятника в честь царствующего дома Романовых. Памятник и сейчас господствует над этой частью города.
В настоящее время на территории бывшего Костромского кремля находится Центральный парк культуры и отдыха, излюбленное место гуляния жителей и гостей города. В 2016 году начато восстановление разрушенных соборов, завершение строительных работ планируется уже в конце 2020 года.
