Leutasch trat urkundlich im 12. Jahrhundert ins Licht der Geschichte. Damals hatten die Edlen von Weilheim im Gebiet der Oberleutasch größeren Grundbesitz, in der Unterleutasch übten hingegen die Herren von Werdenfels Hoheitsrechte aus. Bernhard von Weilheim hat im Jahre 1178 einen Teil seines Besitzes an Wald und Flur in der Oberleutasch dem Augustinerchorherrenstift Polling bei Weilheim geschenkt, das in der Mitte des Tales eine im Jahr 1190 der Hl. Magdalena geweihte Kirche bauen ließ, die 1500 und 1725 erweitert wurde.

Der heutige Bau wurde 1820 / 21 unter Kurat Franz Sieß, der von 1810 bis 1836 die Pfarre betreute, nach dem Plan des Bildhauers und Zeichenmeisters Josef Falbesoner aus Nassereith errichtet und 1831 durch Fürstbischof Galura von Brixen geweiht.

Der stattliche klassizistische Hochaltar gehörte einst zu dem im Jahre 1803 aufgehobenen Kloster Benediktbeuren in Bayern. Die farbenprächtigen, kunstvollen Deckengemälde und das Hochaltarbild stammen von Leopold Puellacher (1776 – 1842). Der massige Baukörper ist kaum gegliedert, die Dachform ist leicht geschweift. Der Turm gehört noch dem früheren Bau an. Die älteste der vier Glocken im prächtigen Turm trägt die Jahreszahl 1482. Das Innere ist ein in Gewölbe unterteilter, reich mit Malerei geschmückter klassischer Saalraum mit Volltonne ohne Stichkappen (Sattelgewölbe).