Gyülekezetünk történetének kezdete egy évszázadra nyúlik vissza. Az 1910-es években, a nyíregyháza környéki bokor-tanyák szlovák nemzetiségű evangélikusai között kibontakozott ébredési mozgalom keltette életre. A mozgalom életre hívói felvidéki misszionáriusok voltak, akik a tanyabokrokba személyesen vitték el az örömüzenetet. A „felébredteknek” nem volt céljuk az evangélikus hitük elhagyása, de a század eleji politikai és társadalmi viszonyok kényszerítették őket, hogy otthont találjanak maguknak. Az ébredés „motorjának” számító Rohacsek József felvidéki evangélistát, pánszláv eszmék terjesztésével vádolták meg, majd az I. világháború kitörésekor kiutasították a városból. Mivel a közösség tagjai Rohacsek eltávolítását az evangélikus klérusának tulajdonították, hátat fordítottak az egyháznak. A gyülekezeti munkát a világháború idején laikusok szervezték, a szolgálatokat is ők látták el. 1920-ban csatlakozott a gyülekezet a metodista misszióhoz. Az akkori szuperintendens 1922-ben Wallrabenstein Jakab volt evangélikus lelkész személyében találta meg a gyülekezet számára megfelelő lelkipásztort. Az ő szolgálati idejében építették fel a gyülekezet kápolnáját, melyet 1923 pünkösdjén szenteltek fel. Wallrabenstein lelkész Kékkeresztes szolgálata, illetve szociális elkötelezettsége kapcsán a gyülekezet nagy megbecsülést szerzett a város vezetősége részéről, mely felejttette a korábbi politikai támadásokat.
Ennek tudható be, hogy 1929-ben Wallrabenstein távozása után, a helyi születésű és erős tót érzelmű Márkus József Andrást helyezték a gyülekezet élére. Márkus idejében erősödött meg igazán a gyülekezeti élet, amit bizonyít, hogy 1932 és 1945 között 177-ről 384-re emelkedett a tagok száma. Ami azért is figyelemre méltó, mert a tagság kérdése a nagy egyházaktól eltérően nem születés szerint, hanem személyes döntés alapján volt anyakönyvezve. Ebben nagy segítséget jelentett a laikus szolgálók lelkesedése, amely a gyülekezet megalakulása kezdetétől fontos szerepet töltött be a gyülekezeti életben. A gyülekezet erősödését csupán a háború utáni csehszlovák-magyar lakosságcsere egyezmény törte meg. Márkus prédikátor erős érzelmekkel állt a szlovák lakosság kitelepülése mellé. Tekintélyét felhasználva győzte meg a gyülekezet nagy részét arról, hogy életüket Szlovákiában folytassák. Szomorú időszak volt ez a gyülekezet életében melynek végén családok szakadtak szét, és a gyülekezet 80%-a kitelepült a szomszédos államba.
A nagy megrázkódtatást szenvedett gyülekezet támaszára, illetve a gyülekezeti élet helyreállítására az egyház vezetése Hecker Ádámot helyezte Nyíregyházára. 1947-57 közötti szolgálata alatt újra megerősítette a gyülekezeti életet, jó talajt készítve utódjának ahhoz a missziói munkához, mely a gyülekezet további erősödését eredményezte.
Hecker Ádámot szuperintendensé választása után, a szolnoki misszió beindításában munkálkodó Iványi Tibort helyezték a gyülekezet élére. Lendületes, missziói elkötelezettségének köszönhetően nagymértékben kiterjesztette a gyülekezet szolgálati területét. A bokortanyákon kívül a hajdúságban, illetve a szabolcsi és szatmári területeken is missziói munkát kezdett el. A gyülekezet növekedése, a misszió bővülése, a kommunista vezetés nemtetszését váltotta ki. A 70-es évektől pedig erős állami támadás célpontjává vált. Az egyház vezetését erős nyomással igyekeztek Iványi Tibor elmozdítására, majd az egyházi szolgálatából való menesztésre. A gyülekezet egy emberként állt az akkor már államellenes tevékenységgel is vádolt prédikátor mellé. Végül az egyház vezetése az állami nyomásra, Iványi Tibor elmozdítása mellett döntött, mely végül szakadáshoz vezetett, mert lelkészek, segédlelkészek, gyülekezetek álltak a lelkész és gyülekezete mögé. Hosszas (1973-81) üldöztetés és meghurcoltatás után az állam új egyházként ismerte el a metodista egyházból kitaszított közösséget, mely 1981.október 1-én Magyarországi Evangéliumi Testvérközösségként lett bejegyezve, melynek egészen haláláig (2009) elnök-lelkésze volt. Iványi Tibor mind a meghurcoltatás mind az elismertetés utáni időben is tovább folytatta a missziói munkát. A nyíregyházi misszióból lett önálló körzet a romák ügyét, és köztük missziói munkát felvállaló Kisvárdai-, és Mátészalkai gyülekezet.
Iványi Tibor helyét és munkáját vette át 1998-ban az 1991-től gyülekezetben munkálkodó Jónás Miklós lelkész, aki jelenleg is a gyülekezet, valamint a mátészalkai körzet missziói lelkésze.