Когда точно построили церковь, историки затрудняются ответить, но предполагают, что каменная церковь в Гродно была возведена в 1140-1170 годы. Сыновья Гродненского князя Всеволода основали храм в честь первых древнерусских святых – князей Бориса и Глеба.
Еще одно название церкви, ставшее гораздо более знаменитым – Коложская – связывают с урочищем Коложань в Гродно, на котором и был построен храм.
Ипатьевская летопись, 1183 года гласит: «Того же лета Городен погоре всь и церквы каменная от блистання молние и шибения грома».
Историки утверждают, что речь в этой записи идет о Борисоглебской (Коложской) церкви, единственном более-менее дошедшем до нас памятнике гродненской школы зодчества. Хотя во второй половине XII века в Гродно существовали еще как минимум две каменные церкви, родные сестры Борисоглебской: так называемая Нижняя (на территории Старого замка) и Пречистенская (на нынешней территории монастыря Рождества Богородицы).
Вторая версия появления этого названия связана с переселением в 1409 году после победного похода князя Витовта на Псков жителей пограничной крепости Коложа.
Большой пожар 1184 года в Гродно уничтожил Нижнюю замковую церковь, и вскоре именно Борисо-Глебская стала главным храмом города.
В течение XIV века в результате многочисленных нападений крестоносцев церковь пришла в упадок, а во время войн с Московским княжеством была значительно повреждена войсками Ивана III. У храма отсутствовала крыша и верхняя часть стен.
И-за оседания грунта, подмываемого Неманом, в 1720 году одна из стен церкви наклонилась, но сползание грунта было остановлено посадкой деревьев. Однако в ночь с 1-го на 2-е апреля 1853 года южная и часть западной стены обрушились. В 1889 году обрушилась южная апсида. В дальнейшем недостающие стены были заменены деревянными.
В советское время Коложская церковь была закрыта для богослужений: в 1948 году передана историко-археологическому музею, а в 1967-м вместе с Замковой горой вошла в состав Гродненского историко-археологического заповедника.
Только в начале 1990-х Коложу вернули Белорусской православной церкви.