Decyzję o budowie nowego kościoła i utworzeniu drugiej parafii na Osiedlu Zielonym w Sokółce podjęto w 1983 r. Biskup Edward Kisiel w 1984 r. powierzył dzieło budowy świątyni ks. Józefowi Kuczyńskiemu. Początkowo na placu kościelnym wzniesiono tymczasową drewnianą kaplicę. Projekt murowanego kościoła przygotowali architekci Hieronim Kiezik i Jerzy Maria Ullman. Ceglany kościół na planie centralnym nawiązuje do architektury ekspresyjnej, w jej prowincjonalnym wydaniu.
Dnia 12 czerwca 1987 r. bp Edward Kisiel erygował parafię pw. Najświętszego Ciała i Krwi Chrystusa, a jej pierwszym proboszczem mianował ks. Józefa Kuczyńskiego. Kamień węgielny poświęcono w 1988 r. W kolejnych latach wzniesiono ściany i dach kościoła. W 1993 r. ułożono posadzkę wewnątrz świątyni, wykonano ołtarz i tabernakulum. Niemal całkowicie wykończony kościół konsekrował 10 października 1993 r. abp Stanisław Szymecki. W kolejnych latach trwało dalsze wyposażanie wnętrza świątyni. W trakcie budowy kościoła wzniesiono także plebanię.