Pirmoji bažnyčia Sedoje pastatyta apie 1508 m. Ją pastatė Dirvėnų tėvūnas Vaclovas Bartasevičius su žmona Elžbieta Juškaite ir aprūpino ją beneficija. 1528 m. minimas klebonas Boguslavas. Sedos pirmoji bažnyčia buvo skirta Švč. Mergelės Marijos Gimimo, Ėmimo į dangų, šv. Vaclovo, šv. Elžbietos ir Švč. Trejybės garbei. Bažnyčios pavadinimas patvirtina faktą, kad jos steigėjai – Vaclovas ir Elžbieta Bartoševičiai.
Bažnyčia yra vėlyvojo baroko epochos žmogaus meninės išraiškos atspindys, lotyniško kryžiaus plano, halinė, su 2 zakristijomis, 5 bokšteliais. Vidus 3 navų, yra 5 altoriai. Šventoriaus tvora akmenų mūro.