В начале 1970-х годов на этом участке земли планировали построить Театр юного зрителя. Был выкопан котлован и вбиты сваи, но в 1980-е годы, из-за нехватки денег, строительство приостановили. В середине 1990-х годов по инициативе Совета ветеранов войны и труда было предложено создать на месте котлована сквер Победы. Он символически был заложен на митинге 8 мая 1995 года. Официально сквер оставался безымянным до 2002 года.

В 2002 году Совет ветеранов войны и труда предложил присвоить этому скверу имя Маршала Советского Союза Г. К. Жукова. Эту инициативу поддержала дочь Жукова, которая в то время находилась в Новокузнецке. Решение о присвоении было принято Советом народных депутатов 23 апреля 2002 года.

Со временем в сквере появились: памятный знак «Сквер имени Маршала Жукова Г. К.», бюст Г. К. Жукова, памятный знак «Побег из ада». В 2005 году кузнецкие металлурги в честь 60-летия Победы заложили в сквере аллею Памяти: 60 молоденьких лип украсили сквер. Ко Дню Победы в 2015 году впервые в городе здесь появился музей военной техники под открытым небом.

Какие бы изменения не претерпевал с годами сквер, он всегда будет хранить память о Великой Отечественной войне для будущих поколений.