Kościół parafialny wzniesiono w latach 1742-1747 (ostatecznie ukończono w 1765 r.) w stylu późnobarokowym. Jego prezbiterium pochodzi natomiast z XV w.
Świątynia posiada cenne wyposażenie wnętrz w stylu rokokowym, w tym niezwykły nagrobek Marii Amalii z Brűhlów Mniszchowej dłuta Jana Obrockiego ze Lwowa (1773). Polichromia na sklepieniu, którą warto zobaczyć, przedstawia sceny z życia i śmierć Marii Magdaleny, a w ołtarzu głównym znajduje się obraz pokutującej patronki kościoła.
Na uwagę zasługuje tabernakulum, a także rzeźby ołtarzowe czterech kobiet uosabiających miłość, wiarę, nadzieję i pokutę. Ambonę zdobią rzeźby czterech Doktorów Kościoła. Na ścianach znajdują się piękne zacheuszki i stacje drogi krzyżowej umieszczone na lustrach. Drzwi do kaplic bocznych wykonane zostały przez drezdeńskich kowali artystów. W przedsionku warto zwrócić uwagę na grobowiec Franciszka Stadnickiego dłuta Jana Obrockiego.
Kościół był wielokrotnie niszczony, w tym w 1944 r. Remontowany w 1954 r. i w latach 1964-65, został gruntownie odrestaurowany w latach 1999-2006.
Wycieczki należy zgłaszać telefonicznie na adres Muzeum Historycznego-Pałac w Dukli (013 433 00 85) lub pocztą elektroniczną (muzeum@dukla.pl).