Lindau wurde 1184 erstmals urkundlich erwähnt. Später wird in einer Urkunde des St.-Peter-Stifts zu Nörten aus dem Jahre 1262 ein Lindauer Pfarrer genannt. Aus dieser Urkunde kann geschlossen werden, dass Lindau damals eine eigene romanische Kirche besaß. Teile des heutigen Turmes und seines Fundamentes sind von dieser Kirche erhalten. Der alte Turm war ursprünglich ein Wehrturm und mit der Kirche nicht verbunden. Er hatte seinen Eingang im zweiten Geschoss, das über eine einziehbare Leiter zu erreichen war. Nach einer gotischen Minuskelinschrift an der südlichen Außenseite des Turmes (neben der Sonnenuhr) wurde 1523 unter Beibehaltung des Turmes ein gotischer Neubau errichtet. Dabei wurde der alte Turm gotisch ummantelt und in den Obergeschossen mit gotischen Fenstern versehen.
Während der Brandschatzung des Eichsfeldes im 30-jährigen Krieg durch Christian von Braunschweig wurde 1626 die gotische Kirche zerstört. Für den Gottesdienst wurde sie zwar notdürftig wieder hergerichtet, verschlang aber nach den seit 1665 vorliegenden Kirchenrechnungen jährlich so viel Geld für Reparaturen, dass man sich im Jahre 1750 entschloss, einen Neubau zu errichten, ebenfalls unter Beibehaltung des Turmes. Begonnen wurde mit diesem barocken Bau aber erst am 17. Oktober 1755 mit der Legung des Obergrundsteins. Aufgrund einer Fehlkonstruktion mussten die ersten Außenmauern des Neubaus wieder zur Hälfte abgetragen werden, da die zu großen Schubkräfte der Dachlast das Mauerwerk auseinander getrieben hatten. Beim Ausbau der Decke stürzte ein Gerüst ein, wobei zwei Arbeiter tödlich verletzt wurden. Die neuen Außenwände wurden doppelschalig-verzahnt ausgeführt und durch insgesamt acht Außenpfeiler gestützt. Der barocke Bau erhielt zwei Türportale, die denen am Mainzer Dom ähneln. Die zur Zierde verwendete Jakobsmuschel am südlichen Portal erinnert an den Jakobsweg, für den es in Lindau eine Raststätte (St. Jakobshospital) gab. Das Untergeschoss des Turmes wurde erst im Jahre 1870 durch Einfügen zweier gotischer Fenster und eines Mauerdurchbruch mit dem Kirchenraum verbunden. Der Turmkopf wurde erstmalig im Jahre 1722, also noch vor dem Bau der heutigen Kirche erneuert und dann nochmals in den Jahren 1806, 1853, 1866, 1890, 1948 und 1994. Bei der letzten Renovierung wurde auch die Kugel neu vergoldet. Den Dachreiterturm erhielt die Kirche im Jahre 1891.
Die Lindauer Kirche ist eine bedeutende barocke Saalkirche. Der Hochaltar in seiner heutigen Form besteht aus mehreren Teilen. Der Steinaltar aus rotem Sandstein stammt noch aus dem Jahre 1759. Der barocke Aufbau des Hochaltars wurde 1883 als Leihgabe an die Diaspora Kirche in Groß-Ilsede gegeben, und kam völlig zerstückelt 1962 zurück nach Lindau. Das Antependium vor dem Steinaltar, eine versilberte Schnitzarbeit, konnte nach mehrjähriger Restaurierung wieder übernommen werden. Es weist durch den Kardinalshut auf Albrecht von Brandenburg, Erzbischof von Mainz und durch die Bischofsmitra auf den aus Lindau stammenden Bischof Dietrich von Brandenburg hin. Das Retabel mit den vier Säulen stammt ursprünglich aus der St. Godehard-Kirche in Hildesheim. Es kam 1863 in die Lindauer Kirche. Die aus Lindenholz geschnitzten Stifterfiguren stellen den hl. Stephanus, Namenspatron von Stephan Boghem von Ehrenfels und die hl. Katharina, Namenspatronin seiner Gemahlin Katharina von Kurzrock dar. Das Wappen dieses Stifterehepaares befindet sich über dem großen Ölbild, das Christus mit den schlafenden Jüngern und den tröstenden Engeln auf dem Ölberg zeigt. Den auferstandenen Christus ganz oben flankieren zwei Engel, die ebenfalls aus Hildesheim stammen.
Eine weitere bemerkenswerte Kostbarkeit in der Kirche ist der auf Leinen gemalte Kreuzweg. Er stammt aus dem ehemaligen Kloster Teistungenberg und kam zu Napoleons Zeiten nach der Säkularisierung des Klosters auf abenteuerlichem Weg nach Lindau. Eine Besonderheit sind auch die beiden holzgeschnitzten Beichtstühle, von denen der rechte Tiara und dem Hahn als Zeichen für den hl. Petrus aufweist. Wertvoll sind ebenfalls die von einem unbekannten Meister geschaffene Kanzel sowie eine Holzstatue der hl. Maria Magdalena (um 1785).
Ende der 1970er Jahre erhielt die Kirche eine Generalrenovierung. Neben notwendigen Außenarbeiten an Türmen und Fenstern wurde im Inneren der gesamte Stuck und die Innenbemalung erneuert. Man versuchte dabei den ursprünglichen Charakter des Kircheninneren aus dem 18. Jahrhundert wiederzugeben. Auch das gesamte Gestühl und die Kanzel wurden renoviert, der Altarbereich wurde gemäß den Vorgaben des zweiten Vatikanischen Konzils umgestaltet. Am 20. März 1982 wurde der neue Altarraum durch Bischof Heinrich Maria aus Hildesheim geweiht. Die Kosten für die Renovierung wurden zu einem beträchtlichen Teil von der Gemeinde getragen.
Bis 1802 gehörte Lindau kirchenrechtlich zu Mainz, danach vorübergehend zu Aschaffenburg und seit 1842 zu Hildesheim.
