История Дворца пионеров началась в январе 1943 г. с нескольких кружков, которые открылись в краевом Доме учителя. Эти несколько кружков и вошли в первый городской Дом пионеров. Первым директором учреждения стал Иосиф Львович Нейтман.
В 1946 г. по решению крайкома партии началась реконструкция здания на проспекте Сталина (ныне Мира), 76. В 1948 г. учащиеся и педагоги отметили новоселье, а вместе с этим сменился и статус учреждения — Дом пионеров стал городским Дворцом пионеров и школьников. В нем занималось порядка двух тысяч детей.
В сентябре 1950 г. во дворце начались занятия по телеавтоматике и по механико-конструкторскому делу, заработал кинолекторий, а в 1952 г. появилась игротека, оборудование для которой воспитанники сделали самостоятельно в мастерских СтройНИИпроекта.
В первые годы работы дворца его лекторами часто становились известные люди края: участники революций 1905 и 1917 гг., ветераны Великой Отечественной войны, основоположники пионерского движения, писатели, художники, ученые. С ребятами встречались писатели Игнатий Рождественский и Николай Устинович, художники Леонид Каратанов, Тойво Ряннель, Борис Ряузов, Леонид Киренский, ставший впоследствии основателем Института физики СО РАН.
В 1957 г. работа дворца впервые вышла на международный уровень. Тогда состоялась дружеская встреча пионеров с делегацией из города Харбина Китайской Народной Республики. От имени китайского комсомола Дворцу пионеров были вручены знамя Китайской Народной Республики и памятный адрес. Воспитанники дворца вручили китайским друзьям знамя РСФСР, памятный адрес и фотоальбом «Красноярский городской дворец пионеров и школьников».
В 1958 г. дворец принимал у себя участников Всесоюзного семинара пионерских работников, и опыт красноярских педагогов дополнительного образования стал известен по всей стране. В 1960-е гг. при игротеке дворца была организована база проката: по договоренности со школой каждый ученик мог получить на дом фильмоскоп, диафильмы, грампластинки или ранец с набором простейших настольных игр.
В 1964 г. кружки отдела художественного воспитания (хоровой, вокальный, балетный, художественного слова, оркестр, ансамбль баянистов) были объединены в пионерский ансамбль песни и танца «Мечта». В 1968 г. возникли первые агитбригады, выступавшие в школах города, на районных слетах, праздниках, комсомольских собраниях. В 1985 г. во дворце была создана региональная детско-молодежная общественная организация «Научное общество учащихся».
В 1986 г. дворец обретает новое собственное здание на Стрелке с большой прилегающей территорией и переходит в краевое подчинение. С 1987 г. на базе дворца работает краевое отделение Российского детского фонда. В 1990 г. начал работу детский международный центр и организационно-массовый отдел, а в 1995 г. зарождается краевой детский парламент.
В 1994—1996 гг. прошло преобразование Дворца пионеров в большую творческую площадку для детей и молодежи. Отделы дворца были преобразованы в центры, наряду с привычными кружками появились школы, студии, клубы, лаборатории. Образовательные программы стали разноуровневыми, рассчитанными на развитие мотивации к познанию и творчеству. Кроме того, дворец стал базой для повышения квалификации педагогов со всего Красноярского края. В 2003 г. дворец был признан лучшим учреждением Сибирского федерального округа в рамках всероссийского конкурса учреждений дополнительного образования.
В 2005 г. был создан Центр информационных технологий и телекоммуникаций, который занимается внедрением ИКТ в управленческую и образовательную деятельность. Сотрудники центра создали дистанционную школу дополнительного образования. В 2009 г. дворец стал победителем всероссийского творческого конкурса на лучшую организацию учебно-исследовательской деятельности и научно-технического творчества учащихся.