Parafia ufundowana została przez Bogoriów i erygowana przypuszczalnie w połowie XIV wieku. Pierwotny kościół parafialny pw. św. Marcina wzmiankowany już w roku 1373 przetrwał jako kaplica do XIX wieku (obecnie Teodorówka). Kościołem parafialnym stał się wybudowany ok. roku 1461 kościół pod wezwaniem św. Marii Magdaleny, o którym mowa w zakładce „kościół”. Parafia należała kiedyś do dekanatu jasielskiego w diecezji krakowskiej.
Po I rozbiorze Polski za sprawą zarządzenia cesarza Józefa II parafia dukielska należała do roku 1785 do diecezji przemyskiej. Później przez 30 lat do diecezji tarnowskiej, a od 1805 roku ponownie do przemyskiej i dekanatu żmigrodzkiego. W okresie międzywojennym utworzony został dekanat dukielski, a proboszczowie parafii byli jego dziekanami.
Do roku 1966 w skład parafii dukielskiej wchodziły: Dukla, Cegowa, Zboiska, Nadole, Iwla, Teodorówka, Lipowica, Nowa Wieś, Hyrowa, Trzciana, Tylawa, Mszana, Zyndranowa i Barwinek.
W 1966 roku wydzielolone zostały z parafii Tylawa, Mszana, Zyndranowa i Barwinek, w 1968 roku Trzciana, a w 1983 Iwla i Hyrowa. W roku 1984 utworzona została parafia przy klasztorze OO. Bernardynów, do której należą Zboiska, część Dukli (do Potoku Dukiełka), Nadole, Cergowa Dolna, Popardy i część Teodorówki (przy drodze w kierunku Gorlic).
Parafię Dukla – Fara tworzą aktualnie Dukla (po prawej stronie Dukiełki), Cergowa, Lipowica, Nowa Wieś i Teodorówka (większa jej część).