Aus der Zeit vor der Reformation haben wir keine schriftliche Kunde der Sankt Gallus-Kapelle von Steinebrunn. Baugeschichtliche Untersuchungen zeigen aber, dass diese Kapelle bereits im 13. Jahrhundert bestanden haben muss. Ihre Glocke stammt aus dem 14. Jahrhundert.
Nach der Reformation und dem 2. Kappeler Landfrieden (1531) wurde die Kapelle den Katholiken zugeschlagen. Doch es gab in Steinebrunn gar keine Altgläubigen mehr. Deshalb blieb das Gotteshaus lange Zeit ungenutzt. Erst um die Mitte des 17. Jahrhunderts – nach einer großen Pestepidemie – siedelten sich in Steinebrunn wieder Katholiken an. Seit 1674 wurde wieder das Heilige Messopfer gefeiert und die Kapelle umgebaut (Weitung des Chorbogens, neue Fenster).
1740 gestattete der Konstanzer Fürstbischof Damian Hugo Kardinal von Schönborn die Errichtung eines Benefiziatenhauses in Steinebrunn. Damit wurde gleich neben der Galluskapelle eine Wohnung für einen ständig anwesenden Seelsorger (Benefizat/Kaplan) geschaffen. Ihm war auch das Schulmeisteramt anvertraut. Mit der Einsetzung eines ortsansässigen Seelsorgers ging 1743 eine erneute bauliche Anpassung der Galluskapelle einher. Die katholische Gemeinde wuchs. Im Jahr 1792 konnte sie mehrere qualitätvolle Kultusgegenstände aus der Schlosskapelle Mammertshofen in Roggwil käuflich erwerben, nachdem dieses Schloss an einen reformierten Besitzer übergegangen war.
1795 erhielt Steinebrunn die Bewilligung zur Errichtung eines Taufsteins und 1842 die Erlaubnis, einen eigenen Friedhof anzulegen. Das spirituelle Leben konnte sich damit weitgehend im Dorf abspielen, nur an hohen Feiertagen wie zum Beispiel Ostern, Weihnachten und Fronleichnam mussten die Steinebrunner noch den Gottesdienst in der Mutterpfarrei Arbon besuchen. 1872 erfolgten dann die definitive Loslösung von Arbon und die Erhebung Steinebrunns zur selbständigen Pfarrei.
Bald zeigte es sich, dass die alte Sankt Gallus-Kapelle nicht die Anforderungen an eine Pfarrkirche erfüllte. Deshalb wurde 1895 eine außerordentliche Kirchenbausteuer eingeführt. Die Gemeinde war sich jedoch noch uneinig, ob lediglich die bestehende Kapelle erweitert oder ein Neubau in Angriff genommen werden sollte. Auch über den Bauplatz wurde heftig gestritten. Pfarrer Alois Scheiwiler (Pfarrer von 1903–1918) regte einen Neubau an erhöhter, weithin sichtbarer Lage auf dem Steinebrunner Winzelnberg an. Als die Kirchgemeinde am 22. Januar 1922 endlich mit 61 zu 30 Stimmen den Neubau einer Kirche auf dem Winzelnberg beschloss, war Scheiwiler freilich bereits von seinem Amt zurückgetreten.
Am 8. August 1922 erfolgte der erste Spatenstich, am 1. Oktober die Grundsteinlegung für die neue Pfarrkirche. Als Architekt war der Rorschacher Albert Rimli beauftragt. Am 13. Oktober 1925 konnte der Solothurner (Basler) Bischof Josephus Ambühl das neue Gotteshaus von Steinebrunn weihen. Es erhielt die Heiligen Gallus und Otmar als Patrone.