Iki XIX a. 7-ojo dešimtmečio Kolainiuose veikė karmelitų vienuolyno bažnyčia, kuri 1867 m. performuota į Viešpaties Atsivertimo cerkvę. 1873 m. įkurta Kolainių Dievo Motinos ikonos „Smolenskaja“ parapija.
Tačiau 1922 m. cerkvė ir 44 ha žemės sugrąžinti katalikams, cerkvė rekonstruota į bažnyčią (Kolainių Švč. Mergelės Marijos, Karmelio kalno karalienės bažnyčia). Kadangi tuo metu Kolainiuose buvo mažai katalikų, bet gyveno daug stačiatikių kolonistų, todėl jie teikė prašymą sugrąžinti cerkvę. Stačiatikiai naudojosi buvusio vienuolyno pastatais. Tuo laikotarpiu mišios laikytos maldų namuose. 1937 m. parapijoje buvo 1753 tikintieji. 1940 metais pašventinta cerkvė, įrengta mediniame gyvenamajame name.
