Am 2. September 1258 wird Parstein zum ersten Mal urkundlich erwähnt. Seit 1267 gehört der Ort zum Kloster Chorin – bis zu dessen Säkularisierung im Jahr 1542.

Der Dreißigjährige Krieg bringt schlimme Verwüstungen, auch die Kirche ist zerstört. 1735 erst wird sie auf den alten Grundmauern wieder errichtet.

Den Aufschwung bringt der Zuzug reformierter Flüchtlinge, insbesondere der aus Frankreich vertriebenen Hugenotten. 1687 kommen die ersten beiden französischen Familien nach Parstein, 1699 sind bereits 16 französische Familien angesiedelt. 

Obwohl von den 30 Bauern- und Kossätenhöfen vor dem 30jährigen Krieg auch 50 Jahre später nur zehn besetzt und bewirtschaftet sind, kommt es zu Spannungen. 1704 verlangen die Kolonisten anderswohin verpflanzt zu werden, „da die Deutschen sie nicht ruhig leben liessen“.

Über 120 Jahre lang gibt es in Parstein zwei Pfarrer: einen lutherischen und einen französisch-reformierten.

1774 leben in Parstein 319 Personen, 1861 sind es 549 Menschen.

Am 13. Oktober 1880 schlägt ein Blitz in den Kirchturm ein.
Turm und Kirche brennen bis auf die Umfassungemauern nieder.

Der Wiederaufbau läßt lange auf sich warten. Erst am 20. Dezember 1887 wird die Kirche wieder eingeweiht.

Weitere zehn Jahre später wird der Turm errichtet.

Am 27. März 1897 wird mit dem Bau begonnen. Am 22. Mai bricht das Bauwerk, das in Feldsteinen aufgeführt worden war, in sich zusammen. Ein zweiter Versuch erfolgt nun in Ziegelmauerwerk. Am 3. September ist Richtfest. Am 3. Dezember 1897 kann der Turm eingeweiht werden.

Seit Ostern 1998 werden Parstein, Lüdersdorf und Bölkendorf von Lunow aus betreut. Das Parsteiner Pfarramt ist aufgelöst.

2001 wird der Innenraum der Kirche originalgetreu restauriert. 2013 wird das Dach neu gedeckt.

2003 leben in Parstein 296 Einwohner von denen 99 zur Evangelischen Kirche gehören.