Heutige Kirche stammt von 1719; typische thüringer Dorfkirche.

1498 wurde die Kirche St. Gangolf gebaut. 1719 erfolgte ein Neubau, bei dessen Ausschachtarbeiten ein Grab mit Münzen aus dem Jahr 1242 oder davor gefunden wurde. Sie ist das geschichtsträchtigste Gebäude des Dorfes. Die Kirche erhielt 1750 eine neue Orgel, die der Orgelbauer Johann Christoph Thielemann begann; sein Schüler Johann Stephan Schmaltz aus Arnstadt vollendete sie.

Ihren Namen hat die Rehstädter Kirche von dem Heiligen Gangolf, dem Schutzpatron der Gerber und Schuhmacher, der Kinder und Haustiere und auch so mancher Quelle.

Gangolf war ein Edelmann am merowingischen Königshof und besaß bei Langres an der Marne ein Kloster. Da dieses unter Wassermangel litt, soll Gangolf eine Quelle gekauft haben, die weit entfernt vom Kloster war, und deren Wasser auf wundersamen Weise zum Kloster geleitet haben. Bereits im 8. Jhdt. soll Gangolf entlang des Rheins von Rittern und Benediktinern verehrt worden sein. Verbreitete Darstellungen zeigen Gangolf als Ritter mit einer Lanze, die eine Quelle öffnet, Schwert und einem Schild, welches ein Kreuz zeigt.