Церковь находилась в предместье Папула (ударение на втором слоге; название теперь неофициальное).
Район Папула расположен к северу от железной дороги. Он вошел в черту города в 1868 г. Отдаленная часть Папулы, по меньшей мере, до конца 1930-х гг. сохраняла характер дачного поселка, а ближе к железной дороге, в восточной части района в конце XIX в. были построены тюрьма (действующая и в настоящее время) и казармы.
Деревянная гарнизонная церковь Тихвинской иконы Божией Матери находилась на Папульской улице (ныне ул. Кривоносова, 9Б). Она была построена в 1905-1906 гг. по проекту архитектора Н.С. Петрова.
В 1918 г., когда Выборг принадлежал независимой Финляндии, в казармах разместился полк Карельской гвардии, православная церковь за ненадобностью была закрыта. В здании разместился юношеский Христианский союз с кружками и секциями. Здание церкви погибло, видимо, в период финской и Великой Отечественной войн (1939-1944 гг.). Теперь на этом месте стоят новые жилые дома.
Земля Невская православная. Краткий церковно-исторический справочник. СПб, "Лики России", 2006, №371. А.А. Смирнов, О.К. Смирнова. Выборгские усадьбы XVIII - XIX веков. Алаборг, СПб, 2009, с. 80. Выборг. Архитектурный путеводитель. Петри Неувонен, Туула Пёюхья, Типани Мустонен. Выборг, "СН". Отпечатано в типографии БЕЛЛ, СПб. 2008, с. 123-125.