Kostel byl postaven pravděpodobně už v polovině 13. století vedle tvrze. První písemná zmínka pochází z roku 1290, kdy v soupisu biskupského majetku jsou uvedeny dva lány, které patřily kostelu. Podle archeologického průzkumu byl kostel opravován po nájezdu husitů v roce 1428. Koncem 15. století bylo rozšířeno zasvěcení kostela o patronky svatou Barboru a svatou Helenu. V roce 1582 byl opraven krov a v roce 1585 byla postavena obvodová hřbitovní zeď. Ve vizitační zprávě z roku 1666 je uváděno, že na střeše kostela byla dřevěná věž se třemi zvony. Po stavbě nového kostela Nejsvětější Trojice a jeho vysvěcení v roce 1725 se stal kostel svatého Kříže filiálním. Pohřbívání bylo přeneslo k novému kostelu a obnoveno bylo v roce 1783. V letech 1859–1860 byl kostel opravován a byla proražena nová okna v lodi. V roce 1901 staticky nestabilní západní zeď byla stržena a znovu vystavěna, byl postaven nový strop v lodi a kruchta.[8] V západním průčelí se nachází kamenná pamětní deska Justuse Wilhelma, kanovníka vratislavské katedrály, kterou vyrobil jesenický sochař Josef Obetha.

V roce 2009 byla opravena sanktusová věž a střecha byla kryta břidlicí. V letech 2013–2014 byly provedeny opravy fasády, stropu, vnitřních omítek a podlahy. V roce 2015 v rámci oprav byl proveden archeologický průzkum kostela, při němž byl mimo jiné objeven hrob kněze. Podle rozboru nalezených kosterních ostatků a dalších fragmentů, s přihlédnutím na dochované seznamy farářů, kteří působili v Javorníku, se předpokládá, že jde o faráře Gabriela Scholze, který působil v Javorníku v letech 1766–1793.[3] Také hrob ženy s dítětem dávají předpoklad, že se jedná o Barbaru Volckmann, která zemřela v roce 1596 a její figurální náhrobek je v průčelí kostela.