1839. gadā Zarasaju pilsētā, kas tajā laikā tika saukta par Novoaleksandrovsku, tika uzbūvēta pareizticīgo baznīca, kam dots vārds Gospodņa. Šajā baznīcā bija daudzas grieķu stilā zīmētas ikonas, saglabāta Dievmātes glezna, kura rotāja Suvieka uniātu klosteri (Suvieko unitų vienuolynas). To uzskatīja par brīnumdarītāju un godināja ne tikai pareizticīgie, bet arī katoļi. 1869. gadā pilsētu apmeklēja M. Muravjeva pēctecis A. Potapovs, un tika nolemts blakus vecajai koka baznīcai būvēt jaunu mūra lūgšanu namu. Veco koka baznīcu 1885. gadā ticīgie pārcēla uz jauno pareizticīgo kapsētas vietu (tagad Valstiečių g.) un iesvētīja to, nosaucot Visu Svēto vārdā.