В XVI веке на этом месте существовал так именуемый Пазрецкий погост, основанный Святым Трифоном с целью распространения православной веры посреди коренных народов — колттов и других саамов. В 1565 году по его инициативе тут была построена древесная однокупольная церковь с колокольней, освящение, как свидетельствует надпись на сохранившемся кресте, проведено 24 июня священником Иларионом. Трифон возлагал надежды с постройкой церкви облегчить свою миссионерскую деятельность, позднее в храме хранилось его рукописное житие. Настоятели погоста жили при церкви только летом, а зимой перебирались в Колу, церковь всегда была бедной из-за малочисленности прихода. Она имела маленький иконостас, на правой стороне которого находились иконы братьев-мучеников и святого равноапостольного князя Владимира с надписями вязью. Близ Пазрецкого погоста была пещера, в какой, по преданию, преподобный Трифон прятался от сопротивлявшихся введению христианства саамов; потом саамами эта пещера почиталась как святыня.
Прихожанами церкви до 2-ой половины XIX века были в большей степени саамы и поморы (летом, в сезон рыбного промысла). Активной просветительской деятельностью посреди колтта-саамов тут занимались такие известные священники как Жора Терентьев (1823—1904) и Константин Щеколдин (1867—1916); они также были одними из первых исследователей истории, культуры и языка коллтов. В 1826 году при демаркации границ Рф и Норвегии граница прошла по реке Паз, и левый сберегал, на котором стоит церковь, отошёл к Норвегии; но ради сохранения православной церкви в составе Рф на норвежском берегу был сотворен анклав площадью 1 км2. Такая конфигурация границы сохранилась до настоящего времени.
23 июля 1870 года Пазрецкий погост посетил величавый князь Алексей Александрович; он выделил средства на ремонт очень обветшавшего строения старенькой церкви, а потом инициировал строительство нового строения храма. Создателем проекта стал инженер Д. В. Васильев. Строительство, курировавшееся особенным комитетом при архангельском губернаторе, велось в 1872—1874 годах. 25 августа 1874 года состоялось освящение храма. 23 июня 1873 года Пазрецкий погост посетили повелитель Швеции и Норвегии Оскар II и царевич Оскар Адольф.
В 1920-х — 1940-х годах территория бывшего Пазрецкого погоста совместно со всем Печенгским районом находилась в составе Финляндии. В 1944 году во время военных действий новенькая церковь Бориса и Глеба очень пострадала, а более старенькый древесный храм сгорел до основания. Храм был восстановлен в 1982—1992 годах, в 1992 году состоялось освящение. По состоянию на 2007 год богослужения в Борисоглебском храме проводились только дважды в год, 15 мая и 6 августа; храм труднодоступен для посещения в связи с нахождением на приграничной режимной местности.
