Die frühe Geschichte von Wangen im Allgäu, das am 26. Juni 815 erstmals urkundlich erwähnt wird, ist eng mit dem Kloster St.Gallen verbunden. Dieses besaß in der Region schon im Frühmittelalter umfangreichen Besitz und errichtete in Wangen einen Kelnhof, der in der klösterlichen Gutsverwaltung eine wichtige Rolle spielte. Über die Entstehung dieses Kelnhofs wissen wir allerdings nichts Genaues. Die Forschung geht von einer Gründung im 9. Jahrhundert aus, was im Hinblick auf die Gütergeschichte des Klosters St.Gallen durchaus plausibel erscheint. Spätestens mit dem Kelnhof dürfte auch die erste (Pfarr-) Kirche von Wangen entstanden sein. Schriftlich fassbar wird diese jedoch erst im Jahr 1182, als ihr Pfarrherr unter den Gönnern des brandgeschädigten Klosters Isny erscheint.
Am 2. Mai 1386 wurde in der Wangener Kirche ein neuer Hauptaltar zu Ehren der Heiligen Martin, Gallus und Christophorus geweiht. Es ist dies der erste Hinweis auf die Kirchenpatrone von Wangen. Eine weitere Weihenotiz ist aus dem Jahr 1421 überliefert, damals mit den Altarheiligen Martin, Gallus, Mauritius, Christophorus und Thomas. Heute steht neben Martin und Gallus der Allgäuheilige Magnus. Dieser wurde wohl im 16. Jahrhundert zum Mitpatron der Wangener Pfarrkirche erhoben, nachdem im Jahr 1524 ein Teil des 1467 in Füssen wiederentdeckten Magnusstabs als hochverehrte Reliquie nach Wangen kam.
Nicht nur die schriftlichen Quellen schweigen über die Frühgeschichte der Wangener Kirche, es fehlen auch archäologische und baugeschichtliche Befunde aus jener Zeit. Die ältesten datierbaren Bauteile der heutigen Pfarrkirche – der untere Teil des Turms sowie die östliche Giebelwand des Mittelschiffs – stammen aus dem 12. Jahrhundert. Diese Bauphase könnte im Zusammenhang mit der Erhebung Wangens zum Marktort stehen, die um die Mitte des 12. Jahrhunderts unter Abt Werinher von St.Gallen erfolgte. Im 13. Jahrhundert entwickelte sich Wangen zu einer Stadt, der König Rudolf von Habsburg 1286 die Überlinger Stadtrechte verlieh. Allmählich emanzipierte sich die Wangener Bürgerschaft vom Kloster St.Gallen, dem sie aber weiterhin den Huldigungseid leistete. Erst seit der Regierungszeit des aus Wangen stammenden Abts Ulrich Rösch sind keine Huldigungen mehr nachzuweisen. Rösch hatte seiner Heimatstadt diese Pflicht wohl großzügig erlassen. Definitiv unabhängig vom Kloster St.Gallen wurde Wangen im Jahr 1608. Damals ging auch das Patronatsrecht der Wangener Pfarrkirche vom Kloster an die Stadt über.
1422 bewilligte der Konstanzer Bischof eine Vergrößerung der Pfarrkirche. Die über dem Westportal angebrachte Jahreszahl 1468 dürfte den Abschluss dieser Bauarbeiten markieren. Im 17. und 18. Jahrhundert wurde die Kirche etappenweise barockisiert, um 1900 dann wieder entbarockisiert und mit einer neugotischen Einrichtung versehen. 1981/82 erfolgte eine große Innenrenovierung, bei der die Kirche unter anderem einen neuen Volksaltar und einen Ambo erhielt.