Pagal projektą buvo numatyta priglausti bažnyčią prie esamos aštuonkampės koplyčios, matyt stovėjusios senosiose Vaidotų kapinėse. Tačiau sumanymas liko neįgyvendintas. Bažnyčia buvo pastatyta 1910 m. dabartinėje vietoje. Ji neteko projekte numatyto aukšto bokšto fasade ir koplyčios, kurios vietoje įrengta Lenskių šeimos kripta. Šiuo metu joje yra penki kapai: bažnyčios fundatoriaus Hilarijaus Lenskio, jo žmonos Marijos Druckių kunigaikštytės (25 III 1852 – 25 I 1924), jų mažamečio sūnaus Ipolito – Polcio († 1879 XII 6), dukters Marijos Magdalenos Haller (1883 III 27 – 1936 VI 4) ir prof. dr. Henriko Reubenbauerio (1881 VI 25 – 1944 10 27).
Bažnyčia neobaroko stiliaus, bazilikinė, kryžiaus formos plano, trinavė. Labai įdomiai suprojektuota jos presbiterija, iš rytų pusės tarsi apgaubta pusapskritimės zakristijos, sukuriant apėjimą aplink didijį altorių kaip romaninėse bažnyčiose. Iškilmingumo ir grožio bažnyčiai suteikia grynos orderinės formos, pagal II Gesu bažnyčios (Roma, Italija) suprojektuotas fasadas. Virš pagrindinių durų įkomponuoti Lenskių ir kunigaikščių Druckių herbai Ostoja ir Druck. Dorėninis orderis suteikia pastatui monumentalumo.
Ant bažnyčios fasado pritvirtinta memorialinė Lenskių šeimos lenta su įrašu: Kościół Nawrócenia Św. Pawła Fundator Hilary Łęski In memoriam Włodzimierz Łęski †1941 Łubianka Moskwa Bronisław Lasocki †1941 w łagrze na Uralu Adelaida Łęska-Lasocka †1941 Kazachstan Daniel Lasocki †1941 Kazachstan R.I.P.
Bažnyčioje yra trys mūriniai altoriai: didysis, Šv. Apaštalo Pauliaus Atsivertimo, su to paties siužeto paveikslu, ir du šoniniai – Švč. Mergelės Marijos Gailestingosios ir Jėzaus Kristaus Nukryžiavimo. Vidaus įranga neobarokinė su neoklasicizmo elementais. Centrinę navą juosia monumentalus frizas; altoriai neobaroko stiliaus; virš durų į zakristiją neoklasicistiniai subraportai ir aplink didžiojo altoriaus paveikslą neoklasicizmo stiliaus lipdyba.
Prie bažnyčios pastatyta varpinė su varpu, kurį 1927 m., padovanojo kun. Stanislav Čyževski (1891–1972).
El. paštas: vaidotu.parapija2020@gmail.com
