В «Путеводителе по всей Сибири и среднеазиатским владениям России» за 1895 г. о красноярском саду сказано, что он лучший не только в Сибири, но и в европейской России. Упоминание сада можно найти и в записках Фритьофа Нансена, побывавшего в Красноярске в 1913 г.: «Цветы уже завяли, но, судя по деревьям, хвойным и лиственным, можно было представить себе, что летом парк являлся чудесным местом для прогулок».
С годами территория парка претерпела изменения в размерах. В 1885 г. с разрешения городской власти значительная часть сада была отдана для постройки духовной семинарии. Затем через городской парк протянулась улица Береговая (ныне улица Дубровинского), отрезавшая его от Енисея. Территория современного кинотеатра «Луч» также прежде принадлежала городскому парку: еще в начале ХХ в. В. А. Поляков построил на этом месте в углу сада капитальное деревянное здание кинематографа «Патеграф». В 1913 г. с восточной стороны сада построили электростанцию, но в 1930-х гг. закрыли.
В 1934 г. Городской сад был переименован в Парк культуры и отдыха имени А. М. Горького. В парке поставили новые ворота, создали аллею, установили различные развлекательные аттракционы и парашютную вышку. В 1936 г. в парке была открыта первая в России детская железная дорога протяженностью 1,3 км.