В 1934 году, с появлением казарм Болотнинского военно-призывного пункта (Дома Обороны) на месте будущей Болотнинской швейной фабрики (современное акционерное общество «Шанс»), часть базарной территории к западу от казарм была превращена в стадион.

К южной части стадиона в это время примыкали остатки бесхозного бывшего сада Минина, расположенные частично на ул. Старокладбищенская (современная ул. Советская).

Восточная часть бывшего сада Минина вскоре была передана в артель инвалидов «Вперед к коммунизму» и позже была застроена домами.

Западная часть бывшего сада Минина получила свое продолжение на север и заняла территорию между ул. Старокладбищенская (Советская), переулком Ленинским, ул. Кооперативная и стадионом. Здесь, на западном входе на стадион, был организован небольшой скверик, который, видимо, сначала не имел своего отдельного названия.

В мае 1944 года забор, лавочки и беседки этого скверика рядом со стадионом были обновлены. В это же время впервые упоминается танцплощадка, расположенная здесь.

25 марта 1947 года Болотнинский городской Совет принял решение создать городской парк культуры и отдыха на месте стадиона. Был составлен проект, по которому бывшая территория стадиона и скверика объединялись.

Через весь парк от ворот на улицу Ленина до ворот на улицу Кирова была проложена аллея, украшенная газонами. Вдоль аллеи с обеих сторон были расположены большие широкие лавочки со спинками, рядом с которыми стояли массивные мусорные урны, по воспоминаниям старожилов, напоминавшие те, что стояли в то время в парках города Новосибирска.

Силами учеников школ № 2 и № 23, студентов педагогического училища и областной школы счетоводов, а также работников отделов горсоветов и сельхозснаба была произведена посадка яблонь, американских кленов, акаций, хвойных и других деревьев в количестве 2300 штук.

Парк был огорожен деревянным забором. По воспоминаниям старожилов, в это время забор и ворота были побелены в белый цвет. Так как болотнинцы активно держали на своих подворьях крупный и мелкий рогатый скот, который по вечерам возвращался с пастбищ по улицам Болотного самостоятельно и не пренебрегал никакой обнаруженной по пути зеленью, для прохода людей в парк были сделаны металлические вертушки, а большие ворота стояли запертыми на замок.

29 июня 1955 года Болотнинский городской Совет передал городской парк клубу им. Кирова (в то время клуб располагался в одной из бывших казарм на углу улиц Кирова и Комарова), парку было присвоено имя Кирова. Южнее центральной аллеи была построена большая деревянная танцевальная площадка с эстрадой, затем перенесенная в юго-восточный угол парка.

Позже танцплощадка была перестроена в капитальное строение из кирпича и бетона, простоявшее на этом месте до начала строительства в парке православного храма во имя Архистратига Михаила Архангела в 2007 году.

Старожилы помнят о тире, который находился на юго-западном углу парка, рядом с парикмахерской (современное здание Совкомбанка) и о продаже мороженого, лимонада и кваса напротив входа в парк - рядом с Центральной столовой № 1 Болотнинского райпо (современное здание магазина «Стиль»). В то же время не являлось секретом, что отдыхающие в парке периодически «утоляли жажду» и напитками горячительными, а за спинками скамеек на аллее всегда можно было обнаружить висящие на ветках разросшегося кустарника стаканы. Тара из-под напитков в то время мусором еще не являлась и поэтому, как правило, сразу же кем-то заботливо подбиралась.

В 1970-х годах парк был обнесен забором из крашеного в зеленый цвет штакетника. В северо-восточной части парка появились аттракционы: «Ладьи», «Ромашка», «Карусель», рядом с которыми был построен «детский городок» из деревянных резных избушки и фигур сказочных персонажей. В этой же части находился общественный деревянный туалет.

9 мая 1980 года в центральной части парка, посредине аллеи, был установлен временный памятник болотнинцам, погибшим в годы Великой Отечественной войны. В 1983 году было принято решение о строительстве на его месте большого мемориала.

В 1984 году происходит перепланировка городского парка, составляется проект. Силами ПМК «Мелиоводострой», МПМК, ПМК-168, Бердских и Приобских электрических сетей были произведены частичная вырубка старых деревьев и корчевание пней, уложен свежий асфальт, установлены новые светильники.

Рабочие мехлесхоза произвели разбивку парка и высадили молодые деревца. Вместо прежнего деревянного забора вагонным депо Болотного было выковано и установлено современное металлическое ограждение парка.

9 мая 1985 года в парке был торжественно открыт большой мемориал в память о погибших в Великой Отечественной войне воинах-болотнинцах.

В июне 1985 года решением исполнительного комитета Болотнинского городского Совета народных депутатов городской парк был передан на баланс комбинату коммунальных предприятий и благоустройства (ККПиБ) с обязательством содержать парк в надлежащем порядке, проводить необходимые работы по его благоустройству, озеленению, сохранности и ремонту мемориального комплекса памяти погибшим воинам-болотнинцам.

Неофициально городской парк стал называться с этого времени «Парк Победы», позже это название перешло в официальное название парка.

24 октября 1987 года рядом с монументом была открыта аллея Героев, на которой были установлены девять бюстов болотнинцев - Героев Советского Союза.

Вероятно, в середине 1980-х годов в парке перестали действовать аттракционы, хотя они и продолжали стоять на своем месте до начала 1990-х годов. Все это время, вплоть до начала 2000-х годов, действовала танцплощадка.

В 1990-х и 2000-х годах в парке произошло несколько случаев вандализма, глубоко возмутившие болотнинцев: с постаментов бюстов болотнинцев - Героев Советского Союза исчезло несколько металлических табличек с именами Героев, выламывались фрагменты фамилий погибших на войне болотнинцев на мемориальных плитах, ломалась часть металлической чеканки на пилонах. В результате с пилонов мемориала была убрана чеканка, на постаментах Героев металлические таблички были заменены на таблички из дешевых материалов.

В мае 2007 года было принято решение построить на месте танцплощадки в городском парке православную церковь, которая задумывалась как знаменательное место, куда смогут приходить люди, вспоминать о погибших воинах и молиться за живых. В местной печати разгорелась дискуссия – что важнее: храм или танцплощадка. В итоге решение построить на месте танцплощадки церковь осталось неизменным, началось строительство. Новая болотнинская церковь возводилась как кирпичный однокупольный храм с шатровой колокольней в русском стиле с элементами эклектики.

21 ноября 2008 года церковь во имя Архистратига Михаила Архангела была торжественно освящена прибывшим из Новосибирска архиепископом Новосибирским и Бердским Тихоном. В настоящее время она является главным православным храмом города Болотное. Кроме нее в Болотном на улице Кондукторская находится деревянная церковь во имя Святого Николая Мирликийского, построенная в послевоенное время.

В 2010 году было принято решение о строительстве нового мемориала на месте старого мемориала воинам, павшим в годы Великой Отечественной войны. В 2013 году начались работы по демонтажу старого мемориала.

 9 мая 2014 года был торжественно открыт новый центральный памятник воинам, павшим в годы Великой Отечественной войны.

Изменения коснулись также аллеи Героев. В 2017 году были убраны старые бюсты и постаменты девяти Героев Советского Союза и на их месте были установлены новые.

Рядом с мемориалом на аллее Героев в разное время были установлены небольшой памятник болотнинцам – воинам-интернационалистам и пушка.

На бывшем месте аттракционов, в северо-восточной части в 1990- годах вновь появилась детская площадка, которая была заново переоборудована в 2010-х годах.

Болотнинский городской парк является мемориальным парком, в котором проводятся памятные церемонии нашей страны. В то же время парк был и остается одним из любимых мест для прогулок и отдыха для болотнинцев и гостей нашего города.