6 июня 1993 г., в праздник Троицы, в кедровом парке Лесосибирска был установлен памятный крест. Во время молебна и установки креста присутствующие заметили в небе крестное знамение — легкие облачка, вытянутые в форме Андреевского креста.
В 1994 г. директор ЛДК-2 Виктор Белорусский решил построить деревянный храм рядом с территорией предприятия на берегу речки Маклаковки. Главный архитектор Лесосибирска Андрей Юревич совместно с красноярским архитектором Александром Банниковым разработал проект деревянного храма. Место под строительство освятил епископ Красноярский и Енисейский Антоний. Однако в это же время генеральный директор ЗАО «ЛДК-1» Анатолий Рубцов, генеральный директор Новоенисейского ЛДК Виктор Шелепков и начальник СМП-3 Владимир Киселев решили начать строительство большого каменного храма. Местом строительства был выбран кедровый парк. Правящий архиерей Красноярской епархии дал свое благословение на строительство нового храма среди молодых кедров на берегу Енисея. Проект нового храма также выполнил Александр Банников.
Строительство с 1995 по 2002 г. вело Лесосибирское СМП № 3 под руководством В. М. Киселева. Финансирование строительства вело ЗАО «ЛДК-1».
Распятие для собора было изготовлено в Троице-Сергиевой лавре, центральный иконостас — в иконописной мастерской отца Шумилова в городе Дубна под Москвой, два других иконостаса — во имя икон Пресвятой Богородицы Владимирской и Страстотерпцев Царя Николая II с Семейством — выполнены мастерами из Новгорода, иконы из мозаики делали челябинские художники В. Качалов и Б. Климов, ранее работавшие над мозаикой в Александро-Невской лавре Санкт-Петербурга, резные аналои делались в Курске.
В течение 15 лет настоятелем собора был прежний главный архитектор Лесосибирска Андрей Юревич. В январе 2011 г. настоятелем Крестовоздвиженского собора был назначен протоиерей Димитрий Харцыз. В мае того же года Енисейская епархия была выделена из состава Красноярской епархии. Управляющим был назначен епископ Никодим.