Заложен парк был в начале 30-х годов XIX века по инициативе костромского губернатора К. И. Баумгартена. Для закладки выбрали участок за зданием Масляных рядов и Городской думы, разрушили крепостной вал и засыпали опоясывавший кремль ров. Планировка: система аллей и дорожек – практически полностью повторяла контуры площадки, в центре располагалась прогулочная зона. Аллеи были украшены беседками и скульптурами, в насаждениях использовались редкие породы деревьев. В 1863 году в парке появилась кондитерская, а также различные увеселительные заведения. 
Парки в СССР – это площадки трансляции культуры и здорового отдыха в массы, каковым постепенно становится и парк им. Ленина в Костроме: в нем появляются киоски и аттракционы, лекторий, скульптуры и памятники, захватывая в 40-е годы и места снесенных соборов.
Сегодня вход в парк есть с двух сторон – со стороны Табачных (Овощных) торговых рядов и с улицы Чайковского. 
Туристов неизменно привлекает памятник В.И. Ленину. Изначально постамент был подготовлен для монумента, посвящённого 300-летию Дома Романовых, но памятник не был завершен и после революции на постамент установили фигуру Ленина.