Parafia powstała z terytorium parafii Zmartwychwstania Pańskiego i parafii św. Kazimierza na mocy dokumentu erekcyjnego z 27 czerwca 2005 r. wystawionego przez abp. Wojciecha Ziembę. Ostatecznie granice nowej placówki duszpasterskiej ukształtowały się po korektach, wskutek których oddzielono niektóre ulice do parafii sąsiednich. Pierwszym proboszczem został ks. Tadeusz Krawczenko, od 1990 r. rządca parafii Zmartwychwstania Pańskiego i budowniczy tamtejszego kościoła. On to, po kolejnym pożarze kościółka św. Kazimierza na cmentarzu św. Rocha, który miał miejsce 14 czerwca 1999 r., już 14 października tego roku rozpoczął wykopy pod nowy kościół budowany według projektu inż. arch. Michała Bałasza. W styczniu 2004 r. zakończono prace wykończeniowe wewnątrz świątyni. Neobarokowa budowla z elementami neorenesansowymi i secesyjnymi posiada wyniosłą elipsoidalną kopułę widoczną w panoramie tej części miasta. Polichromie wykonał Jerzy Pasternak. W głównym ołtarzu, naśladującym ołtarz z kaplicy Matki Boskiej Ostrobramskiej, umieszczono kopię wileńskiego obrazu z Ostrej Bramy pędzla Bogusława Leona Lorka, który jest też autorem stacji Drogi Krzyżowej. Dnia 8 września 2007 r. na obraz w ołtarzu głównym podczas zorganizowanej na tę okoliczność uroczystości parafialnej korony nałożył metropolita białostocki abp Edward Ozorowski w asyście kard. Henryka Gulbinowicza z Wrocławia, abp. z Moskwy Tadeusza Kondrusiewicza i biskupa warszawsko-praskiego abp. Sławoja Leszka Głódzia.
Równocześnie z budową świątyni, ks. T. Krawczenko przebudował plebanię i rozpoczął wznoszenie ogrodzenia wokół całego cmentarza grzebalnego i dzieło to niechybnie by dokończył, gdyby 28 sierpnia 2008 r. po długiej i ciężkiej chorobie nie przestał był zdobić tego świata. Jego następcą został mianowany 10 października tego roku ks. Henryk Radziewicz. Jeszcze tego samego miesiąca abp E. Ozorowski dokonał aktu przeniesienia własności cmentarza z parafii św. Rocha do parafii Wszystkich Świętych. Pierwszą inwestycją nowego proboszcza było doprowadzenie wody i kanalizacji do kościoła. W latach następnych prowadzono prace przy układaniu alejek na cmentarzu, zamontowano instalację wodną i monitoringową oraz dokończono prace przy ogrodzeniu cmentarza i kolumbarium. W roku 2012 podziemia świątyni zostały obudowane wypełnioną szkłem konstrukcją aluminiową, zaś w rok później przeprowadzono termomodernizację plebanii i inne drobniejsze prace remontowe.
Kapłani pracujący w parafii
od czasu jej powstania (2005 r.):
- ks. Tadeusz Krawczenko (proboszcz) 2005-2007 r.
- ks. Józef Hakało od 2005 r.
- ks. Kazimierz Mikłasz od 2005 r.
- ks. Adam Szczesiul od 2005 r.
- ks. Dariusz Łuczaj od 2005 r.
- ks. Henryk Radziewicz (proboszcz) 2007-2015 r.
- ks. Krzysztof Kowalewski od 2007 r.
- ks. Andrzej Grajewski od 2007 r.
- ks. Alfred Romanowski od 2008 r.
- ks. Tomasz Piotrowski od 2011 r.
- ks. Rafał Arciszewski od 2012 r.
- ks. Wojciech Szubzda od 2013 r.
- ks. Tomasz Roszkowski od 2013 r.
- ks. Dariusz Kłagisz od 2014 r.
- ks. Adam Artur Anuszkiewicz od 2015 r.
- ks. Grzegorz Kłoczko (proboszcz) 2015-aktualnie
- ks. Marcin Hołodok od 2015 r.
- ks. Sławomir Laskowski od 2016 r.
- ks. Michał Skowroński od 2019 r.
- ks. Konrad Węcławski od 2019 r.
- ks. Wojciech Dziubiński od 2020 r.
- ks. Karol Cimoch od 2021 r.
- ks. Karol Piniewski od 2021 r.