Инициатива постройки русского храма в Вене принадлежит протоиерею Михаилу Раевскому, который с 1842 по 1884 годы был настоятелем венской посольской церкви. Он исходатайствовал разрешение и в 1867 году начал сбор пожертвований на строительство большого каменного православного собора. Однако смерть, последовавшая в мае 1884 года, не позволила ему стать очевидцем осуществления его замысла. Денег собрали немного — 22000 рублей хватило лишь на маленький кладбищенский храм.
Закладка храма состоялась 8 сентября 1893 года на отведённом для погребения русских участке Центрального кладбища Вены. Выстроена в русском стиле по проекту М. Т. Преображенского. Строителем был местный архитектор Вагнер. Освящение храма состоялось в 27 апреля (9 мая) 1895 года. Храм был приписан к собору святого Николая в Вене, освящённому в 1899 году.
В течение многих десятилетий храм не реставрировался и к концу 1990-х годов пришел в аварийное состояние, в результате чего был закрыт городскими властями. Реставрационные работы в храме начались осенью 2004 года по инициативе епископа Венского и Австрийского Илариона (ныне митрополит Будапештский и Венгерский) и велись в течение двух лет под руководством Вольфганга Цехетнера на частные пожертвования из России. 12 октября 2006 года митрополит Смоленский и Калининградский Кирилл (ныне Святейший Патриарх Московский и всея Руси) совершил великое освящение храма.
Протоиерей Радослав Ристич, назначенный в 2008 году настоятелем храма, рассматривал этот приход, где он каждую субботу совершал литургию, как небольшую часть общего венского прихода. В летний период, когда в соборе святителя Николая было меньше богослужений, верующие особо приглашались помолиться в Лазаревский храм. В Лазареву субботу, на престольный праздник храма, совершается крестный ход вокруг храма.
Храм относится к Венской и Австрийской епархии Русской Православной Церкви.