Tõstamaa kirikust on esimesi teateid 17. sajandist, mil viidatakse Kastnas olnud kabelile. 17. sajandi lõpuks oli kabel juba viletsas seisus ning on teada, et Tõstamaale ehitati uus puidust kirik, kus jumalateenistusi peeti ligi 100 aaastat. Kivikirik otsustati ehitada Seep (Sepp?) Mardi maale, mille kinkinud Tõstamaa mõisa omanik assistentsnõuniku abikaasa Anna von Helmersen. Peale kiriku koha sai uus kirik veel ½ adramaad maad ja vabastuse kõigist maksudest. Tõstamaa kiriku nurgakivi asetati 1763. aastal. Kirik ehitati aastatel 1763-1768. Esimene kirikuõpetaja, kelle kohta on kohapeal andmeid, on Tõstamaal Ludwig Raspe (1662-1663). Tõstamaa kiriku torn ja esikülg koos oreliga  varisesid aleviku kanalisatsioonitrassi ehitustööde tõttu 1972. aasta jaanilaupäeval. Õnnetuses keegi  viga ei saanud.  Rahvasuus on levinud arvamus, et kui kõrts olnud külas enne kirikut, siis kirik ei püsivat. Tõsi on see, et kohalik Ranna kõrts asus keskalevis ning jäi mujalt tulijaile enne ette kui kirik.

20. sajandi alguses asus kiriku vastas peale vallakooli ka kohalik piirivalvekordon, mille õppeplats oli kohe kiriku kõrval Värati-poolsel küljel.

Praegune Tõstamaa Maarja luteri kirik ehitati maakividest aastatel 1763 – 1768 Pärnu ehitusmeistrite juhtimisel. Kiviseinad krohviti ning välisnurkadesse maaliti mitmevärviline rustika. Laes on säilinud laud, millel aastaarv 1767 ja kiri “Soli Deo Gloria”- ainult jumalale au. Kirikusaali katab peegelvõlvalagi, mida 1888. aastal uuendati ja kivikatuse asemele paigaldati sindlikatus. Kirikutorn oli tähtis maamärk Kihnu väinas.

Kiriku sajandaks aastapäevaks (1863) kingiti praegune altarimaal ja puunikerdustega kantsel- kohaliku meistri töö. Viimane orel pühitseti 1885. Kiriku kell on valatud Riias 1861.aastal. Kirikus on mälestustahvlid kirikuõpetajale, õpetajapouadele ja mõisnikule, samuti mõisahärra pink. Hoone on ehitatud vesiliiv pinnasele, mistõttu juba 19. sajandil hakkasid külgseinad vajuma. Võimaliku varingu vältimiseks ehitati seinu toetavad tugipiilarid. 1972. aasta jaanilaupäeval varisesid kanalisatsioonitrassi kaevamistööde tõttu torn ja esikülg ning hävis ka orel.

1983. aastal alustati taastamistöödega. Aastaks 2000 sai kirik oma praeguse näo, puuduvad veel tornikiiver ja kukk. Kirikul on aktiivne kogudus.