Bereits 1784, drei Jahre nach Herausgabe des Toleranzpatentes, erbauten die protestantischen Salzarbeiter in Hallstatt ein Bethaus mit 355 Sitzplätzen.

Das einfache Gebäude ohne Turm und Glockengeläut wurde aus Bruchsteinen errichtet und an der Seeseite auf Piloten (Holzpfähle) gesetzt. Es stand am linken Mühlbachufer, unmittelbar bei der Mündung des Baches in den See. Gekennzeichnet war es durch ein an der Seeseite angebrachtes Kreuz.

Dieses protestantische Bethaus wurde der stark angewachsenen evangelischen Glaubensgemeinschaft in Hallstatt bald zu klein.

Daher begannen die evangelischen Christen im Jahr 1859 mit dem Bau der Christuskirche. Ermöglicht wurde die Finanzierung auch durch große Opfer der eigenen Gemeinde, aber hauptsächlich durch Spenden von Wohltätern wie den Fürsten von Hohenzollern-Hechingen und der Fürstin Therese von Thurn und Taxis sowie vom Gustav-Adolf-Verein.

Zunächst wurden zwei alte Salzfertigerhäuser angekauft und abgetragen. Auf deren Grundstück, nun auf der südlichen Seite des Mühlbaches gelegen, errichtete man dann in fünfjähriger Bauzeit die Christuskirche mit ihrem 53 m hohen Glockenturm. Der Bauplan stammte von Professor Ludwig Lange (1808–1868) aus München.