Hajnówka, pierwotnie zwana Hajnowszczyzna (Haynowszczyzna), pod względem kościelnym od 1501 r. do 1777 r. należała do parafii Kamieniec Litewski. W latach 1777-1866 stanowiła część dzisiejszej parafii Narewka, będącej wówczas filią parafii Jałówka. Po upadku powstania styczniowego w 1863 r. i po likwidacji parafii w Narewce Hajnówka została przyłączona do parafii Szereszewo w powiecie prużańskim. W tych granicach pozostawała od 1866 do 1914 r., kiedy to ponownie powstała parafia w Narewce, w skład której weszła również Hajnówka.
Parafia Hajnówka została erygowana 3 maja 1923 r. przez ks. Jerzego Matulewicza (1871-1927), biskupa wileńskiego (1918-1925). Jej pierwszym proboszczem (do 1934 r.) został ks. Antoni Mioduszewski (1885-1971). W maju 1923 r. urządził on tymczasową kaplicę w budynku poniemieckiego kina. Kaplica ta służyła wiernym do 9 maja 1936 r., kiedy to - razem z dzwonnicą - uległa pożarowi, przypuszczalnie podpalona przez aktywistów komunistycznych.
W 1936 r. z inicjatywy parafian została zbudowana kolejna, prowizoryczna kaplica z muru pruskiego pod kierunkiem ks. Pawła Stepka (1877-1953) ówczesnego proboszcza hajnowskiego (1934-1939). Nabożeństwa były odprawiane od 25 grudnia 1936 r. do 2 września 1963 r. Nowy murowany kościół pw. Podwyższenia Krzyża Świętego został wzniesiony wokół dotychczasowej kaplicy według projektu arch. Stanisława Marzyńskiego z Warszawy. Budowę zainicjował 23 lutego 1946 r. ks. Józef Moniuszko (1887-1958), proboszcz hajnowski (1939-1947). Wznoszenie fundamentów zostało rozpoczęte 28 sierpnia 1948 r., a już 14 listopada ks. prał. Henryk Humnicki (1873-1959), wikariusz kapitulny diecezji pińskiej (1946-1950), poświęcił kamień węgielny. Jednak władze komunistyczne zablokowały budowę. Prace wznowiono dopiero 14 września 1957 r. staraniem ks. Ignacego Wierobieja (1896-1970), proboszcza hajnowskiego (1947-1970).
2 września 1963 r. poświęcił on prezbiterium i odprawił pierwszą Mszę św. Wznoszenie gmachu obecnej świątyni zakończono 27 listopada 1965 r.
W okresie duszpasterskiej posługi (1970-1996) ks. kan. Alfonsa Trochimiaka (1934-1996) zostały wstawione m.in. witraże oraz została wykonana mozaika w absydzie świątyni (1977) według projektu Wiktora Zina z Krakowa. Staraniem obecnego proboszcza ks. Mariana
Świerszczyńskiego w 2001 r. została zakupiona działka po byłym dworcu PKS, dzięki czemu plac przykościelny został znacznie powiększony.
Obok kościoła, po drugiej stronie ul. Ściegiennego, stoi piętrowa, murowana plebania, wzniesiona w latach 1978-1980 według projektu arch. Grażyny Nasierowskiej z Białegostoku. Pracami budowlanymi kierowali: ks. kan. Alfons Trochimiak i ówczesny wikariusz (1972-1982) ks. Kazimierz Siekierko. W 1983 r. został zbudowany budynek katechetyczny według projektu Tadeusza Mroza z Hajnówki, staraniem ks. kan. Alfonsa Trochimiaka.

Bibliografia:
J. E. Kulpa, Zarys historii parafii rzymskokatolickiej w Hajnówce (1923-1993), Drohiczyn 1994 (mps).

Kaplice:
Hajnówka - kaplica szpitalna pw. Matki Bożej Uzdrowienia Chorych w Zespole Opieki Zdrowotnej w Hajnówce. 16 maja 1997 r. została poświęcona przez bp. Antoniego P. Dydycza.
Porządek Mszy św.:
- niedziele i święta:
- kościół parafialny: 7.00, 8.30, 10.00, 11.30, 18.00.
- w szpitalu: w sobotę o 16.00; na oddziale chorób płucnych i zakaźnych - niedziela o 16.00
- święta niebędące dniami wolnymi od pracy:
- kościół parafialny: 7.00, 10.00, 18.00
Odpusty w parafii: św. Stanisława Biskupa Męczennika - 8 maja; Podwyższenia Krzyża Świętego - 14 września
Nabożeństwo adoracyjne: początek w III niedzielę Adwentu
Księgi metrykalne:
Księgi Chrztów: od 1923 r.
Księgi Małżeństw: od 1923 r.
Księgi Zmarłych: od 1923 r.