История Приютненской церкви и её прихода началась с 50-х годах XIX века, когда на калмыцкие земли вблизи озера Амтя-Нур на основании указа императора Николая I от 30 декабря 1846 года «О заселении дорог на калмыцких землях Астраханской губернии» прибыли государственные крестьяне из Екатеринославской, Воронежской, Харьковской и других губерний. В 1857г. приютяне поняли, что они уже в состоянии построить храм и взять его и причт на свое полное обеспечение.
11 октября 1857 года Черноярский окружной начальник Ведернинов доложил в Астраханскую палату государственных имуществ, что поверенные от станицы Приютной государственные крестьяне Тимофей Кулаков и Иван Шапошников обратились к нему с ходатайством разрешить обществу построить деревянную церковь во имя «Воздвижения Животворящего Креста Господня». На строительство храма у крестьян имелось 2 тысячи рублей серебром. 4 ноября 1857 года прошение с аналогичной просьбой поступило на имя епископа Астраханского и Енотаевского Афанасия (Дроздова). Свое желание иметь храм крестьяне обосновали тем, что ближайшее от них культовое сооружение находилось в 30 верстах в станице Крестовой (ныне село Первомайское Ремонтненского района Ростовской области).
Астраханская духовная консистория с пониманием отнеслась к желанию приютян иметь свой храм и причт. До окончательного устройства церкви и причта, к ним был послан заштатный Черноярский священник Анатолий Ташлинцев, который стал первым духовным лицом в истории села Приютного. Но в 1859 году, в связи с выселением крестьян из станицы, строительство храма замедлилось. В атмосфере неопределённости относительно будущего поселения в 1860 году крестьяне приняли решение приостановить постройку церкви и ограничиться сооружением молитвенного дома.
Первое культовое здание села Приютного – Крестовоздвиженский молитвенный дом – появилось в 1860 году и обошлось оно его жителям вместе с церковной утварью в 400 рублей серебром. Через три года строительство храма возобновилось. 18 октября 1863 года сельский сход постановил приступить к постройке новой церкви, которая была завершена в 1867 году.
В 30 годы ХХ века храм был закрыт и отдан под зернохранилище, позже церковь превратили в клуб. А верующим вместо отобранной и поруганной церкви отдали дом, находящийся неподалёку. Туда перенесли иконы и продолжали молиться.
Пришли новые времена, и стал вопрос о возвращении храма его истинным хозяевам. Был объявлен сбор средств на реставрацию храма. Прихожане, коллективы, организации, предприятия, колхозы вносили свои вклады. Но случилась беда: в июле 1992 года по неизвестной причине восстанавливаемый храм сгорел. Районное руководство того времени пыталось решить вопрос по строительству новой церкви. Он строился с мая 1993 по май 1995 года при личной материальной поддержке К.Илюмжинова, бывшего тогда президентом Калмыкии, а также на пожертвования верующих.
7 июля 1997 года в храме побывал Святейший Патриарх Алексий II, находившийся с визитом в Калмыкии. Его Святейшество преподнес в дар храму икону Казанской Божией Матери.
Источник: сайт храма http://priyutnoe.prihod.ru/home/history/