Єдина пам’ятка дерев’яної архітектури Кам’янця-Подільського — Хрестовоздвиженська церква — розташована в каньйоні, попід замком у давньому передмісті з незвичною назвою Карвасари. Свого часу місто було на перехресті торгових шляхів, які вели з Європи на Схід, з Московії на Балкани. Назва «Карвасари» походить із тюркської «караван-сарай» — місце, де зупинялися каравани купців, які йшли до міста. Сплативши мито, торговці прошкували попід скелею каньйону, щоб через Руську браму піднятися у верхнє місто.

Перша згадка про церкву святого Хреста для русинів відноситься до другої половини 17 століття. Про це також свідчить гравюра Кіпріана Томашевича. Під час турецького нашестя 1672 року святиню зруйнували.
На початку 18 століття на Карвасарах на місці руїни будується дерев’яна церква. У 1799-1801 роках після перебудови її споруда набула того вигляду, який зберігся до нашого часу і, зокрема, зафіксований на літографії Наполеона Орди другої половини 19 століття. Отож, храм — типова для Поділля тризрубна споруда, зразок продовження народних традицій української дерев’яної архітектури більш раннього часу.
Загалом діючою церква була до 1953 року. 1960 року частину ікон передали в музей, а решта церковного майно зникла. 1964 року храм пристосували під… кінотеатр.
 Із 1970 року будівля церкви почала поступово руйнуватися. Невідомий зловмисник виломив вхідні двері, і в будівлю був вільний доступ.
На щастя, 1988 року бюджетним коштом (майже
60 тисяч карбованців) під егідою Львівського філіалу інституту «Укрпроектреставрація» на церкві завершили ремонтно-реставраційні роботи. Згідно з проектом в першу чергу перенесли об’єм дзвіниці. Щоб зберегти якомога більше старих конструкцій каркаса, її частково перенесли автокраном. Реставрації передували калібрування, деталювання дерев’яних конструкцій. Непридатні деталі реставрували шляхом вставок і доповнень з нового матеріалу. Нові деталі виготовляли з врубками за старовинними зразками. Особлива складність виникла в процесі роботи, коли влаштовували перехід від чотиригранного зруба до восьмигранного.
При демонтажі дзвіниці, коли знімали шалівку обшивки, реставратори виявили сліди від підкосів голосникового ряду, які повторюють форму центральних збережених голосників. Таким чином відкрили по чотири голосники на кожній грані, а не по два, як передбачалося.
Складність реставрації Хрестовоздвиженської церкви полягала ще й у тому, що реставратори вперше зіткнулися з роботою такого характеру. Проте комплексна ланка теслярів-реставраторів у складі В. Заганича, В. Білого, І. Єфремова під керівництвом майстра В. Гурника успішно справилася з поставленим завданням. Споруда донині перебуває на балансі Національного історико-архітектурного заповідника «Кам’янець».
Лише 22.11.1990 року рішенням виконавчого комітету Кам’янець-Подільської міської ради № 411 Хрестовоздвиженську церкву передано релігійній громаді віруючих Української православної церкви. Перше богослужіння провів отець Лаврентій Кобля.
З 1991 по 1996 роки настоятелем церкви служив Микола Сухов. Весь цей період його помічницею була Майя Голінберг (перша староста храму). Церковна громада виконала великий обсяг з ремонту інтер’єру, облаштувала іконостас.
Упродовж 1996-2006 років новий настоятель отець Іван Буряк продовжив відродження храму.
З 2006 року і донині настоятелем Хрестовоздвиженської церкви служить ієрей Тарасій Тимків. Народився він 1975 року в селі Виноград Івано-Франківської області. Закінчивши філософсько-теологічний факультет Чернівецького університету імені Юрія Федьковича, декілька років працював викладачем цього вишу. З ініціативи священика впорядковано територію храму. Біля нього споруджується двоповерхова будівля, в якій розташуються недільна школа і будинок милосердя.
На узвишші здіймається до неба символ духовної столиці Поділля 15-метровий Хрест, виконаний з металу на пожертви віруючих міської громади художником — ковалем Ростиславом Пугачем. Автор цього ескізного проекту — отець Тарасій Тимків. Освячено Хрест на честь 210-ї річниці побудови церкви.