Около церкви с древних времён существовал причал для перевоза через реку Великую. Церковь построена в XY веке, каменная, ранее была монастырской. Климентовский монастырь впервые упоминается в летописи под 1354 годом, в 1615 году разорен шведами - здесь стояла их осадная артиллерия, и упразднён. По указу Псковской духовной консистории в 1786 году к ней приписана каменная церковь Святителя и Чудотворца Николая бывшего Кожина монастыря (от Кож, не сохранилась). В 1883 году церковь передана в ведение Псковского духовного училища. В 1893 году, до построения воинской церкви Святого Александра Невского, Климентовская церковь была в ведении Омского полка. В начале ХХ века церковь поддерживалась на средства церкви Святителя Николая Кожина монастыря. Для богослужений из Николаевской церкви приносилась церковная утварь. В церкви были два престола: главный - Святого Климента Папы Римского и Святого Патриарха Петра I Александрийского, южный, как и притвор, устроен во второй половине XYIII века - Воздвижения Честнаго и Животворящего Креста Господня. Археологические раскопки 1973 года показали, что с северной стороны в древности также был придел. Церковно-приходского попечительства, богадельни, больницы и школы при церкви не было.  

Церковь закрыта 2 апреля 1924 года. В годы Великой Отечественной войны церковь получила частичные повреждения кровли, стен, наружной и внутренней отделки. 31 октября 1995 года городская администрация передала церковь верующим. 9 августа 2003 года состоялся первый крестный ход от храма Александра Невского к церкви Климента, которая стала храмом военных моряков и всех работающих в портах, в том числе на реках. Однако средств на ремонт храма у верующих в настоящее время нет.

Адрес церкви: Ольгинская набережная, д. 16.