Über den Ursprung der Kirche von Gestratz erzählt nur eine Legende: Die Gestratzer hätten ihr Gotteshaus zuerst auf der Anhöhe Schweineburg errichten wollen. Doch als unsichtbare Hände nachts das Tagwerk immer wieder ins Tal trugen, erkannte die Gemeinde den Fingerzeig Gottes und erbaute die Kirche im Dorf.
Schriftlich tritt die Gestratzer Kirche 1275 erstmals in Erscheinung, und zwar im berühmten Liber decimationis der Diözese Konstanz. Sie gehörte damals den Grafen von Montfort, die den Besitz von den Grafen von Bregenz übernommen hatten. Diese Bregenzer Grafen, die dem bedeutenden Adelsgeschlecht der Udalrichinger angehörten, waren möglicherweise die Gründer der Gestratzer Kirche, die wohl von Anfang an dem heiligen Gallus geweiht war. Die Udalrichinger gehörten zu den wichtigen weltlichen Förderern des Galluskults, spätestens seit mit Abt Purchart I. (958–971) einer der Ihren dem Kloster St.Gallen vorstand. (Neben Gestratz sind wohl auch die Galluspatrozinien von Grünkraut, Bregenz und Tettnang auf die Initiative der Udalrichinger zurückzuführen.)
Die Grafen von Montfort übergaben die Gestratzer Kirche im Jahr 1361 ihrem Hauskloster Mehrerau, das ursprünglich ebenfalls eine Gründung der Udalrichinger Grafen von Bregenz war. Nur das Patronatsrecht behielten sich die Montforter noch bis 1528 vor. Grünkraut gehörte zu den einträglichsten Pfründen der Region, wovon auch die Patronatsherren profitierten.
Eine wichtige baugeschichtliche Notiz findet sich im Gestratzer Jahrzeitbuch (Anniversar) von 1538: Die alte Kirche sei 1435 infolge ihres hohen Alters eingestürzt und daraufhin innerhalb von zwei Jahren in Mauern, Dach und sieben Fenstern fast vollständig neu errichtet worden. Am 2. Juli 1437 nahm der Konstanzer Weihbischof Johannes die Weihe der neuen Pfarrkirche vor und stellte den Hochaltar unter das Patronat von Sankt Gallus sowie weiterer Heiliger. Die Weiheurkunde ist bis heute im Pfarrarchiv von Gestratz erhalten geblieben.
Schon bald nach dem Neubau, während der Amtszeit von Pfarrer Johannes Strölin (1437–1472), wurde die gesamte Kirche mit Fresken ausgemalt. Nachdem diese längere Zeit übermalt waren, kamen sie anlässlich einer Kirchenrenovierung im Sommer 1934 wieder zum Vorschein. Der bedeutende spätgotische Bildzyklus, der in seinem ursprünglichen Zustand erhalten werden konnte, stellt das Marienleben und das Leben Jesu dar.
Ebenfalls während der Amtszeit von Johannes Strölin könnte die Kirche in den Besitz jener sagenhaften Kreuzreliquie gelangt sein, die eine bedeutende Wallfahrt nach Gestratz begründet haben soll. Wir wissen allerdings kaum etwas Sicheres über Wallfahrt und Reliquie. Die Schweden, so wird erzählt, hätten dem Gestratzer Pfarrer 1632 den wertvollen Kreuzpartikel gestohlen, worauf die Wallfahrt versiegt sei. Die Feinde, so berichtet der Pfarrer, hätten übel gehaust: »Von der Früh bis zum Abend haben sie gesotten und gebraten, gesoffen und gefressen und alle Kisten und Kasten zusammengeschlagen.« Die Sankt Gallus-Kirche musste 1663 neu geweiht werden. In der Folge wurde das Gotteshaus kontinuierlich an die Bedürfnisse der Gemeinde und den Geschmack der Zeit angepasst. 1730 wurde das Kirchenschiff um etwa vier und 1866 um etwa acht Meter verlängert, um der gestiegenen Bevölkerungszahl Rechnung zu tragen.
Ihr heutiges inneres Aussehen hat die Gestratzer Pfarrkirche Sankt Gallus in der zweiten Hälfte des 20. Jahrhunderts erhalten. Feuchtigkeit hatte dem Bau stark zugesetzt und eine Renovierung dringend nötig gemacht. Dabei ging fast die gesamte Ausstattung, die zwischen 1866 und 1911 mit viel Aufwand entstanden war, verloren. Die pilzbefallenen gotischen Fresken konnten 1985 gerettet werden.