Überlieferungen, die erst im 18. Jh. Aufgezeichnet wurden, lassen die Kirche zu Altaussee (mundartlich „Altenaussee“) gegen Ende des 12. Jh.s erbaut sein. Erst etwa hundert Jahre später ist sie im Gesamturbar Albrechts I. ausdrücklich bezeugt. Eine weitere Tradition meint, sie sei älter als die Pauluskirche von Bad Aussee und eine ehemalige Pfarrkirche. Tatsächlich hatte sie längst vor der Errichtung einer eigenen Seelsorgestelle die pfarrlichen Rechte: Die Ausseer Pfarrordnung von 1483 setzt das Begräbnisrecht voraus,  Nachrichten aus dem 17. und 18. Jh. erwähnen einen Taufstein und die Spendung der Ostersakramente, und das gotische Sakramentshäuschen bezeugt die Aufbewahrung der Eucharistie. Die urkundlichen Erwähnungen setzen 1433 ein, die Jahreszahl 1434 sieht man als Bauinschrift an der Westseite neben dem heutigen Hauptportal.

Auch das Ägidiuspatrozinium weist auf die Entstehung im 12. Jh. hin, aus dem die meisten Ägidiuskirchen des Landes stammen und in dem mit der Schenkung von zwei Salzpfannen an die Cisterze Rein durch den Markgrafen Ottokar 1147 die Urkunden über die Salzgewinnung am Ahornsberg einsetzen. Wurde die „Bergkirche“ etwa für die Salzarbeiter erbaut? Dann stünde sie wohl nicht am Seeufer, sondern näher bei den ältesten Stollen und Salzpfannen (gegen Lupitsch hin).

Die Sage weiß zu berichten, der vordere Teil der Kirche sei uralt und einst ein heidnischer Götzentempel gewesen. Dagegen spricht das Ägidiuspatrozinium, das es in der Missionszeit noch kaum gab. Oder sollte Ägidius einen älteren Kirchentitel „abgedrängt“ haben, etwa auf einen Seitenaltar? Ein solcher war bis ins vorige Jahrhundert dem hl. Martin geweiht. Mit diesem Kirchenpatron wäre ein Heiligtum tatsächlich schon im Frühmittelalter denkbar. Freilich gibt es eine viel einfachere Erklärung für die Sage: Die Kirche hatte bis 1859 im Presbyterium ein Pflaster von Quadersteinen, im Schiff aber von Ziegeln. Vielleicht hielt man die Steinquader für antik und „heidnisch“.

Sagen und Vermutungen können freilich nicht darüber hinwegtäuschen, dass wir für die Kirche „St. Gilgen zu Vischarn“, wie die frühesten Bezeichnungen im 15. Jh. lauten, erst gegen 1300 sicheren Boden unter die Füße bekommen. Innerhalb des Ausseerlandes scheint tatsächlich die Gegend um den Altausseersee älterer Siedlungsboden zu sein. Fischereirechte sind an diesem See von Anfang an privat, im Gegensatz zu den herrschaftlich-landesfürstlichen am Grundlsee, und nur vor den Altausseer Fischern (wie auch von denen am „Goisersee“ – Hallstättersee) bezog das Kloster Traunkirchen als Lehensherr der Kammergutspfarren eine jährliche Reichung von Fischen. Die alten pfarrlichen Rechte galten für einen genau abgegrenzten Bezirk, die Gottesdienste wurden von der seit 1301 bezeugten Pfarre (Bad) Aussee besorgt. Erst Kaiserin Maria Theresia stiftete 1770 ein eigenes Vikariat, das in manchen Dingen (z.B. Prozessionen an Dreifaltigkeit und Fronleichnam) noch von der Mutterpfarre abhängig blieb. Das wurde auch dann erst langsam anders, als das Vikariat 1892 zur selbständigen Pfarre aufgestiegen war.