Bereits in der zweiten Hälfte des 11. Jahrhunderts wurde in Hall eine Kirche errichtet, wahrscheinlich kurz nach der Gründung der Benediktinerabtei Admont (1074). 1095 erfolgte die Weihe dieser ersten Kirche durch den Salzburger Erzbischof Thiemo. Diese frühe Errichtung einer Kirche in Hall hängt mit der bereits vorhandenen Infrastruktur für den Salzabbau zusammen, der dem Ort auch seinen Namen gab. Die erste Kirche in Hall dürfte bereits dem Heiligen Kreuz geweiht gewesen sein und blieb eine Filiale der großen Mutterpfarre St. Amandus in Admont. Patres des Stiftes Admont versehen seither die Seelsorge in Hall, wenngleich bis ins frühe 17. Jahrhundert nur an Freitagen Gottesdienste gefeiert wurden (diese Freitagsgottesdienste haben sich bis heute erhalten). Regelmäßige Messfeiern an Sonn- und Festtagen sind erst ab 1675 belegt.
Die Heilig Kreuz-Kirche wurde in der Neuzeit immer wieder verschiedensten Renovierungs- und Umbauarbeiten unterzogen. Maßgeblich waren hierbei die Arbeiten in der ersten Hälfte des 18. Jahrhunderts, die dem Kirchenbau seine gegenwärtige Gestalt verliehen. Zu Beginn des 20. Jahrhunderts wurde der barocke Tabernakelaufbau (Veit Königer, 1776) aus der Pfarrkirche hl. Bartholomäus in Landlnach Hall übertragen. Wenig später erwarb man auch die dazu passende Barockmonstranz.
Im Zuge von Renovierungsarbeiten im Inneren (1984) wurden an der Altarwand Seccomalereien aus dem 18. Jahrhundert entdeckt, die man freilegen konnte. 1995 wurde die 900-Jahr-Feier der Kirche in Hall begangen. 2013 wurde die Kirche im Innenbereich ausgemalt und teilweise umgestaltet. Zeitgleich erhielt der Kirchturm ein neues Holzschindeldach und eine vierte Glocke; auch das Turmkreuz wurde erneuert. 2014 erfolgte schließlich die Gesamt-Außenrenovierung der Kirche. Seit 2015 bildet die Pfarre Hall bei Admont mit der Pfarre Frauenberg an der Enns und Ardning einen Pfarrverband.
Die Haller Heilig Kreuz-Kirche wurde im Laufe der Jahrhunderte mit Reliquien ausgestattet, die einen Bezug zum Leiden und Sterben Jesu haben und die Ziel von Wallfahrern und Pilgern wurden. Erwähnenswert sind die beiden großen Reliquienschreine am Hochaltar, mit zwei Berührungsreliquien (Lanze und Nagel). Außerdem eine Monstranz mit einem Partikel vom Kreuz Jesu. Dieser wurde 1703 von Leonhard Graf Moggau der Haller Kirche geschenkt und in einer Monstranz (aus dem Stift Göss) gefasst.
In der Barockzeit sind große Wallfahrten nach Hall belegt: Gaishorn am See, Sankt Gallen, Weng im Gesäuse und Admont. Regionale Wallfahrten kommen bis heute nach Hall.