Первый храм в мест. Векшни был освящен во имя преп. Сергия в 1867 г. в помещичьем доме с помощью Свято-Николаевского Ковенского братства, впоследствии пожертвовавшего для церкви часть утвари. 24 июня 1871 г. цесаревичем Александром в приход была пожертвована икона свят. Петра, митр. Киевского. Горордок получил активное развитие с прокладкой в 1871-1873 гг. Либаво-Роменской железной дороги.
Новая одноглавая каменная церковь заложена в престольный праздник 1871 г. и освящена 20 июля 1875 г. благочинным прот. Василием Круковским при настоятеле свящ. Михаиле Баталине. Ее архитектура соответствует образцовому проекту К.А. Тона – трехчастной церкви в имении Синявина. Отличием храма являются два мощных ризалита под щипцовыми крыльями, примыкающие по сторонам к основному кубическому объему храма. Сдвоенные арочные окна на них оформлены профилированными тягами и завершены килевидными кокошниками, как и окна на полуциркульной в плане алтарной апсиды и трапезной в 1 ось. Килевидным кокошником завершен и перспективный портал. Декор представлен поясами сухариков и бегунца. Сохранился выбеленный позолоченный двухъярусный иконостас с чертами классицизма и русского стиля.
В середине 1870-х гг. мировым посредником В.Н. Семчевским в приходе было образовано попечительство, среди жертвователей были уездный предводитель дворянства граф В.Н. Зубов, владелец имения «Медемрод», калужанин П.Ф. Трунёв, местные жители – литовцы. Действовала церковно-приходская школа с общежитием для бедных девочек на 20 человек.
В память спасения семьи императора Александра III 17 октября 1888 г. в 1889 г. прихожанами был заказан киот с иконой пророка Осии и преподобномученика Андрея Критского. Почиталась Козельщанская икона Божией Матери.
В 1891 г. храм был ремонтирован, в 1892 г. – построена новая колокольня. На 1898 г. в приходе насчитывался 1021 человек, в него входили жители русских деревень Попеляны, Саварины, Окляны. На отдельно расположенном православном кладбище похоронены благотворительница фрейлина Д.В. Моро-Олсуфьева и начальник станции Муравьево (Мажейки, Мажейкяй) П.Н. Яковлев.
С 1932 г. настоятелем служил свящ. Александр Чернай, впоследствии архим. Алексий, с именем которого связано возрождение прихода. Осенью 1943 г. в приход были эвакуированы 3000 человек из Новгородской области. Вместе с благочинным прот. Василием Николаевским в Векшняй доставили раки с мощами Новгородских святых из Софийского собора: святителя Никиты, благоверных князей Владимира и Феодора и княгини Анны, части мощей свят. Иоанна и преп. Антония Римлянина. В конце ноября – начале декабря 1944 г. они были возвращены в Новгород и затем помещены в запасники музея. В 1944 г., когда приход насчитывал 678 человек, советской артиллерией была снесена колокольня и разрушена на 75% кровля, прот. Александр эмигрировал в США. Службы в храме возобновились в 1947 г. Настоятелем в 1951-1981 гг. был священник Александр Сташенко. Храм был ремонтирован в 1953-1954, 1970 гг. В 1958 г. построен приходской дом. При игумене Несторе (Шмидте) храм был приписан к церкви в Тельшяй, в 1995-1998 гг. проведен ремонт, в 2001 г. в упрощенных формах восстановлена колокольня.
прот. Александр Берташ