Am Standort der heutigen Pfarrkirche gab es im Mittelalter bereits ein Hospiz, neben dem später eine Kapelle erbaut wurde und das erstmals im Jahre 1331 in einem Ablassbrief erwähnt wurde. Die Kapelle befand sich zu dieser Zeit noch im Bau und wurde erst einige Jahre darauf, am 12. September 1336, geweiht. Schon damals war der Hl. Jodok ihr Patron, die Jungfrau Maria wurde bald darauf ebenfalls in einigen Dokumenten als Patronin erwähnt.

Als Erbauer der Kapelle gilt Ekkehard von Villanders, ursprünglich Lehensinhaber der Trostburg und ab etwa 1320 auch Herr der Trostburg. Vermutlich waren das Hospiz und die Kapelle als eine Folge des zu dieser Zeit stetig zunehmenden Verkehrs errichtet worden.

Die heutige Gestalt erhielt die Pfarrkirche Waidbruck durch einen Umbau (vielleicht auch Neubau) in den Jahren 1647 bis 1649, welcher unter Conrad Dietrich von Wolkenstein, damaliger Herr der Trostburg, vom Meister Ambrosi Oberhofer durchgeführt wurde. Ihre Weihe erhielt die Kirche am 25. Oktober 1649 durch den Brixner Bischof Jesse Perkhofer.

Anfang des 20. Jahrhunderts bemühte man sich zu Beginn um einen Neubau, wobei man allerdings auf Widerstand von der örtlichen Gemeindeverwaltung stieß. Für Waidbruck allein sei die Größe der Kirche ausreichend. Jedoch zählte die spätere Pfarrei Waidbruck ungefähr dreimal so viele Mitglieder wie die Gemeinde Einwohner und die bestehende Kirche fasste nur rund 100 Gläubige. So begann man im Jahre 1929 mit den Erweiterungsarbeiten, bereits ein Jahr darauf konnten sie vollendet werden. Sie erfolgten unter dem Kuraten Heinrich Schweigkofler. Die Entwürfe dazu fertigte der Bozner Architekt Marius Amonn an, die Innenarbeiten stammen von dem Kunstmaler Rudolf Complojer.

Um 1957 wurde das Gotteshaus unter Kurat Anton Platter durch den Malermeister Siegfried Valtingojer ein weiteres Mal restauriert.

Neuerliche Renovierungsarbeiten am Außen- und Innenraum der Pfarrkirche erfolgten im August 1976. Dabei traten alte Fresken zum Vorschein, die das Denkmalamt daraufhin fachmännisch freilegte.