Городской голова Иван Андреевич Милютин стал инициатором посадки в Череповце большого городского общественного сада. На территории будущего парка находились соляные склады купцов, и это место называлось «Соляной городок». Потом за этим местом закрепилось название «Соляной сад», бытовавшее еще долго.
Разбивку и планировку парка И.А. Милютин поручил Николаю Ивановичу Бернику — преподавателю черчения Александровского технического училища. Сад предполагалось заложить в классическом, регулярном стиле. Земля для парка была выкуплена городской управой. Часть денег вложил лично И.А. Милютин, в связи с этим появилось второе название — «Милютинский сад».
В 1892 году в парке открыт «Народный дом» (постройка из бревен с террасами и балконами), где показывали туманные картины, выставки промыслов, велись курсы по кухневодству и практическому огородничеству. В доме читались публичные лекции, проходили собрания городской общественности, обсуждались важные проблемы. Официально сад был открыт в 1897 году.
В 2020 году парк культуры и отдыха выиграл грант в конкурсе Минстроя, в 2021 году началась реконструкция. Месту было возращено его историческое название — «Соляной сад». В парке появился зеленый лабиринт, установлены новые арт-объекты, беседки с прудом, интерактивная площадка «Соляные холмы», свободная библиотека, зона воркаут, теннисные столы, гигантские шашки и шахматы, гамаки и шезлонги, новые торговые павильоны и полторы тысячи новых деревьев и кустарников.В Соляном саду установлен единственный в области уличный парковый экран, что позволило показывать кино на отрытом воздухе.
В парке работают муниципальные аттракционы: железная дорога «Метро», карусель «Юла», карусель «Чайный сервиз», детский батут, электромобили, веломобили, детский призовой аттракцион «Рыбалочка».