В августе 1996 года в село Яшалта для организации общины был направлен священник Михаил Бабкин.
В 1997 г. администрация района выделила здание под церковь — заброшенный магазин культтоваров, построенный в 1952 году.
8 сентября 1997 года в день празднования мучеников Андриана и Наталии была совершена первая Литургия. Вместе с богослужениями началась реконструкция здания. Работы решено было производить в три этапа: строительство колокольни над входом в здание, реконструкцию алтарной части, реконструкцию центральной части.
Священник вместе с верующими приложил много сил, чтобы приспособить здание для богослужений. Сначала был пристроен алтарь, затем возведена колокольня. Летом 2004 года над Яшалтой раздался колокольный звон. Все село принимало участие в праздничном освящении колоколов, которое совершил архиерей.
Церковь в Яшалте — единственная в Калмыкии, оборудованная механизированной колокольней.
К настоящему времени реконструирована алтарная апсида и центральная часть храма.
Приписные храмы:Церковь Успения Пресвятой Богородицы села Веселое Яшалтинского района.
Источник: сайт храма http://adrian-natalia.prihod.ru/home/history/