Suomen itsenäistyttyä kannettiin huolta itärajan väestön aineellisesta ja henkisestä hyvinvoinnista. Suomen hallitus loi eduskunnan toimeksiannosta 1924 rajaseutuohjelman kyseisten syrjäisten alueiden hoidon tehostamiseksi. Työn tavoitteena oli rajaseudun asukkaiden omatoimisuuden ja isänmaallisen hengen kehittyminen. Rajaseututyöhön osallistui valtiovallan ja aatteellisten rajaseutuyhdistysten ohella myös kirkko. Kuusamosta tuli ensimmäinen seurakunta, jonka alueella Suomessa aloitettiin kirkollinen rajaseututyö alueineen ja pappeineen.
Aluksi ehdotettiin uuden seurakunnan perustamista. Siihen olisi kuulunut Kuolajärven (Salla) ja Kuusamon alueita. Näiden pitäjien alue oli melkein kaksi kertaa Uudenmaan läänin kokoinen ja niissä toimi vain kolme pappia. Tuotiin myös esille, että Paanajärvellä oli kommunistiagitaation vuoksi epävakaa yhteiskunnallinen tilanne. Tavoitteena oli, että valtio olisi ottanut vastuulleen pappien palkkauskustannukset. Oulun hiippakunnan tiedustellessa asiaa Kuusamon seurakunnalta, vastaanotto oli hyvin myönteinen. Kirkonkokous esitti alueeseen Paanajärveä, Liikasenvaaraa, Suorajärveä, Vuotunkia, Kuntijärveä, Vatajärveä, Tavajärveä ja Välijärveä Kuusamon pitäjästä sekä Kuolajärveltä Sovajärveä ja Tuutikylää. Alueen keskuspaikaksi esitettiin Paanajärveä.
Kirkko päätti 1931 sijoittaa rajaseutupapin Paanajärven kylään ja opetusministeriö päätti alkuvaiheessa palkkakustannusten rahoituksesta viideksi vuodeksi. Pastori Toivo Laitinen aloitti työn Paanajärvellä syyskuussa 1931. Opetusministeriö määritteli rajaseutupiirin, joka oli pituudeltaan 100 kilometriä ja leveydeltään 50 kilometriä. Siihen kuului Kuusamon seurakunnasta kolme kinkeripiiriä: Paanajärvi, Tavajärvi sekä Vuotunki mukaan lukien Suoraniemen ja Ervastin talot Alakitkan kinkeripiiristä. Kuolajärveltä rajaseutupiiriin luettiin Tuutijärven ja Sovajärven kylät.
Vuonna 1934 aloitettiin varojen kerääminen kirkon rakentamiseksi Paanajärvelle. Metsähallitus lahjoitti 200 tukkipuuta, jotka kyläläiset kokosivat ja sahauttivat yhdessä papin kanssa. Toivo Laitisen siirryttyä 1935 Puolangan kirkkoherraksi, rajaseutupapiksi tuli hänen veljensä Olavi Laitinen. Varsinainen rakentaminen alkoi kesällä 1936. Hanke toteutettiin pääasiallisesti kyläläisten talkootyönä. Vuonna 1937 kerättiin koko Suomen alueella yhden sunnuntaipäivän kolehti Paanajärven kirkon hyväksi. Kirkko vihittiin käyttöön 9.9.1937.
Paanajärven alue mukaan lukien sen kirkko tuhoutuivat talvisodassa 1939 ja koko Paanajärven alue menetettiin lopullisesti jatkosodan päättyessä. Rajaseututyö jatkui kuitenkin sotien jälkeen. Uusi rajaseutukeskus tuli Käylään. Sinne rakennettiin myös uusi rajaseutukirkko, joka vihittiin käyttöön 14.12.1958. Etelä-Kuusamon Poussun ja Lämsän kylien alueelle muodostettiin Murtovaaran rajaseutupiiri.
Rajaseutupiirien kirkolliseen toimintaan kuuluivat jumalanpalvelusten ja kirkollisten toimitusten järjestäminen. Yhtenä arvokkaana osana kuusamolaista rajaseututyötä toimivat rajaseutusisaret terveydenhoidon ja diakonian työalalla.
Rajaseututyö seurakunnissa päättyi 2002 lopussa, ja toiminta tuli kyseisten seurakuntien vastuulle.