Храм был построен в период с 1999 по 2003 год и освящён в 2003 году митрополитом Смоленским и Калининградским Кириллом.
Строительство храма было инициировано для духовного окормления пациентов Смоленской областной клинической психиатрической больницы, расположенной в Гедеоновке. В 1911 году при больнице была учреждена домовая церковь, однако после Октябрьской революции деятельность подобных учреждений была прекращена. В конце XX века возникла необходимость воссоздания духовного центра для пациентов и персонала больницы. 2 октября 1999 года митрополит Кирилл освятил основание нового храма.
При строительстве церкви была использована деревянная церковь в честь Изнесения Честных Древ Животворящего Креста Господня, ранее находившаяся на улице Рыленкова в микрорайоне Поповка. После завершения строительства каменного храма в честь Новомучеников и Исповедников Российских, деревянная церковь была перенесена в Гедеоновку и адаптирована под новый храм.
Архитектурно храм представляет собой деревянное здание, выполненное в традициях русского православного зодчества. Внутреннее убранство храма включает иконостас и иконы, соответствующие канонам Русской Православной Церкви. В церкви хранятся частицы мощей святых благоверных князей Феодора Смоленского и его сыновей Давида и Константина.
С момента освящения храм стал центром духовной жизни не только для пациентов и персонала психиатрической больницы, но и для жителей посёлка Гедеоновка и окрестных населённых пунктов. В храме регулярно проводятся богослужения, а также мероприятия, направленные на духовное просвещение и поддержку прихожан. 9 апреля 2024 года в храме прошло приходское собрание, на котором обсуждались вопросы богослужебной жизни прихода, взаимодействия с образовательными учреждениями и другие аспекты приходской деятельности.
2 октября 2016 года в храме состоялся престольный праздник, посвящённый дню памяти святого благоверного князя Феодора Смоленского и его сыновей Давида и Константина. В этот день была совершена Божественная литургия и крестный ход, в котором приняли участие прихожане и паломники из Смоленска и других благочиний Смоленской епархии.