Nynější podoba města Javorník se historicky vyvíjela ve dvou celcích, kterými bylo město pod hradem a ves. Starší z těchto celků, ves označovaná již od počátků jako Javorník, se formovala kolem tvrze a nedaleko ležícího kostela sv. Kříže. Její vznik můžeme na základě písemných i archeologických pramenů datovat zhruba do období okolo poloviny 13. století.

Také počátky existence samotného kostela je možno klást, podobně jako založení vsi, před 60. léta 13. století. V listině vidnavského fojta, datované do r. 1291, opírající se ale o starší listinu z r. 1266, je uváděna „Bernardova ves blízko Jawirniku“. Je tedy zřejmé, že Javorník již v 60. letech 13. století existoval a byl natolik fungující a stabilní sídelní jednotkou, že bylo možno na něj odkazovat. Lze tedy předpokládat, že již v této době, tak jak to dokládají i výsledky stavebně-historických průzkumů, zde mohl stát také farní kostel sv. Kříže. První přímá písemná zmínka o kostelu je z r. 1290, kdy mu, podle soupisu biskupského majetku, patřily dva lány.

V závěru 15. století bylo patrocinium kostela rozšířeno o zasvěcení sv. Heleně a sv. Barboře. O statut farního kostela přišel kostel sv. Kříže při stavbě nového kostela sv. Trojice ve městě. Roku 1723 se stal kostel sv. Kříže hřbitovním kostelem. Jelikož byl roku 1725 vysvěcen kostel ve městě, u kterého vznikl hřbitov, na přilehlém hřbitově se plně pohřbívalo znovu od roku 1783, kdy byl hřbitov ve městě již zcela opuštěn.

Od svého vystavění prošel kostel několika přestavbami. Nejvýraznější, historicky doložené z vizitačních zpráv, jsou přestavby z let 1859 – 1860 a z roku 1901. V letech 1859 – 1860 byly strženy boční kůry a předsíň a kostel byl nově vydlážděn, vymalován, dostal novou krytinu střechy kostela a věže. Vyroben byl i nový oltář. Roku 1901 byla ze statických důvodů stržena západní zeď a znovu vybudována. Při této znovuvýstavbě západní zdi byl vyroben nový strop v hlavní lodi a kruchta.

Bohatá vnitřní fresková výmalba byla odhalena a restaurována v letech 2016 - 2022.