Храм преподобной Евфросинии Полоцкой на православном кладбище г.Вильнюса строился по благословению архиепископа Полоцкого и Виленского СМАРАГДА, в течение года. Закладка церкви состоялась 9 мая 1837 г. Летом 1838 г. строительство было закончено, и церковь освящена. В грамоте владыки Смарагда говорилось, что церковь строится по желанию местных жителей на суммы доброхотных дателей. В числе этих "доброхотных дателей" был известный человек своего времени "благоговейный муж" купец Тихон Зайцев, который пожертвовал на обустройство кладбища и приведение его в должный порядок 4000 рублей. В дальнейшем было собрано еще 8000 рублей, после чего и решился вопрос о строительстве на кладбище своего храма.
На средства Тихона Зайцева, согласно его завещанию, впоследствии были сооружены богадельня, административное здание, часовня-усыпальница на месте упокоения сего мужа.
В 1865 г. стараниями сыновей члена государственного совета генерала Ф.А. Панютина церковь была переделана.
В 1881 г. сооружен каменный притвор, а в храме на средства купца Жмуркевича были установлены две кафельные печи.
До 1896 г. кладбище и храм, находились в ведении св. Николаевского кафедрального собора, когда последовал Указ Святейшего Синода о назначении самостоятельного причта к церкви преподобной Евфросинии.
В 1904 г. при первом же настоятеле о.Александре Карасеве был произведен капитальный ремонт храма: достроены алтарная часть, ризница, колокольня, певческие хоры, перестроены своды и купол, установлен новый иконостас. Освящение церкви после ремонта совершил архиепископ Никандр.
С 1923 г. по 1937 г. св. Евфросиньевская церковь была объединена с Ново-Светским св. Александровским приходом. Настоятелем объединенного прихода стал о.Михаил Кушнев, а вторым священником - о.Лев Савицкий.
До 1948 г. кладбище со времени постройки на нем храма находилось в церковном ведении.
В 1948 г. оно было национализировано, и храм остался только лишь приходской единицей. В это же время были национализированы и все строения, принадлежавшие приходу (в их числе - четыре жилых дома).
Настоящий внутренний вид храма - это результат капитального ремонта: с росписью купола, алтаря, написанием новых икон на стенах, - который произведен в тот период, когда настоятелем в нем был о.Леонид Гайдукевич (1973 - 1976 гг.).
25 июля 1997 г. для участия в торжествах, связанных с празднованием 650-летия свв. мучеников виленских Антония, Иоанна и Евстафия и 400-летием Свято-Духова монастыря, в Вильнюс прибыл Святейший Патриарх Московский и всея Руси АЛЕКСИЙ II.
26 июля 1997 г. произошло историческое событие в жизни нашего прихода - Его Святейшество посетил наш приход. Святейший Патриарх обратился со словами приветствия к собравшимся, осмотрел храм, отслужил заупокойную литию у входа в св.Тихоновскую часовню, помолился за захороненных в братской могиле у мемориального комплекса, беседовал с народом, преподал святительское благословение каждому желающему.
В храме преп. Евфросинии Полоцкой служили священнослужители:
- о.Александр Карасев (1896 - 1911);
- о.Иоанн Энтсон (1911 - 1919);
- о.Михаил Кушнев (1919 - 1927);
- о.Лев Савицкий (вторым священником, 1923 - 1949);
- о.Иоанн Красновский (1927 -1936);
- о.Феодор Шипица (вторым священником, 1933 - 1934);
- о.Нил Кульчицкий (1936 - 1954);
- о.Феодор Ракецкий (вторым священником, 1949 - 1950);
- о.Василий Недвецкий (вторым священником);
- о.Александр Недвецкий (1954 - 1974);
- о.Леонид Гайдукевич (1973 - 1976);
- о.Николай Устинов (1976 - 1980);
- о.Вячеслав Сковородко (1980 - 1989);
- о.Владимир Ринкевич (с 1989 г.); диакон Игорь Ринкевич (1997 - 2004).
Есть еще одна святыня на кладбище - часовня св.Георгия Победоносца. Сооружена она по проекту академика Чагина в соучастии с профессором Императорской академии художником Резановым, на месте захоронения русских солдат и офицеров; освящена в 1865 г. В настоящее время нуждается в капитальном ремонте.
В богадельню, построенную при приходе в 1848 г., принимались нищие и изувечные. Помещения были рассчитаны на 12 человек. Богадельня просуществовала до 1948 г., когда церковные дома были национализированы.
В 1991 г. по инициативе православных людей г.Вильнюса городские власти передали кладбище в заведование приходской общине.
У восточной стены кладбища есть братское захоронение (1151 человек) военнопленных и мирных жителей - жертв Второй Мировой войны. В 1997 г. по инициативе ветеранов войны и при содействии посольства России в Литве на месте захоронения сооружен мемориальный комплекс. Открытие комплекса произошло 30 апреля. Освятил братское захоронение архиепископ Виленский и Литовский ХРИЗОСТОМ.
На кладбище захоронены братия Св.-Духова монастыря, сестры женской обители, священники, диаконы, известные люди своего времени и времени настоящего, такие как: академик, директор Виленской рисовальной школы И.П.Трутнев; профессор и литератор П.В.Кукольник; военный юрист, литератор, "последователь доктора Гааза" А.В.Жиркевич; общественный деятель, писатель В.А.фон Роткирх (Теобальт); поэт, ученый и педагог Я.Ф.Головацкий; однокашник М.Ю.Лермонтова и его сослуживец мемуарист М.И.Цейдлер; племянник Кутузова полковник П.Г.Бибиков.