Това е един от най-малките храмове във Варна, но е сред най-старите оцелели по възраст. Малката църква, строена като семеен параклис, e с основи, които датират от XIV век.
Храмът "Св. Параскева" е построен през 1785 г. по времето на тогавашния Варненски гръцки митрополит Филотей, със средства на гръцката фамилия Роде. Роде бил търговец и пренасял стоките си с кораб по пътя Венеция-Цариград-Варна-Кюстенджа. При едно от пътуванията си попада в морска буря и дава обет, че ако оживее, ще построи храм в чест на Св. Параскева. След благополучното си завръщане, гръцкият търговец изпълнява обещанието си - закупува място за строеж на църква срещу къщата си (къщата съществува и до днес, в нея се помещава Музеят на историята на Варна). Предвид забраните за строителство във височина на християнските храмове в годините на турското робство, църквата е вкопана в земята с четири стъпала.
Около сто години след построяванeто на църквата, тя се нуждае от основен ремонт. Инициатор за събиране на средства за ремонта е една бедна вдовица на име Евтимия. Тя събира пари от къща на къща и след дълъг и упорит труд църквата е възстановена в благоприличен вид. От построяването си до 1914 г. храмът се обгрижва от гръцки свещеници, след което започват да служат и български. Църквата никога не е имала собствена енория, а се е обгрижвала от духовници от други варненски храмове. Първите български свещеници са от катедралата. От 1924 г. в храма започва да служи о. Йордан Светославов от старинен храм "Успение Богородично". През 1938 г. в храм "Св. Параскева" идва о. Георги Иванов - началник на Социални грижи към св. Митрополия.
В периода от 1939 г. до 1962 г. тя била предоставена на руски имигранти и е обгрижвана от архимандрит Кирил Попов. От 1962 г. до 1965 г. църквата е обгрижвана от пенсионираните свещенослужители архим. Инокентий, прот. Георги Доганов и прот. Стефан Йорданов.
На 1 Март 1965 г. храм "Св. Параскева" се поема от българския свещеноиконом Иван Вълков след неговото пенсиониране. Храмът спешно се нуждае от ремонт, а средства за такъв няма. Със своя ентусиазъм и благочестие о. Иван успява да привлече много християни, които с усърден труд започват да възстановяват сградата.
При наближаване на 200-годишнината на храма (1985 г.), той отново се нуждае от възстановяване. Отец Иван, уповавайки се на Божията помощ, се заема с ремонта. Организира работници и майстори, които безвъзмездно успяват да извършат възстановяването на храма. Подновяват църквата, препокриват я и я обзавеждат с всичко необходимо. Жилищната сграда, която също била рухнала се подновява. И така обновен храмът посреща тържествено своята 200-годишнина. На празничната света Литургия о. Иван е награден с офикия - ставрофорен иконом.
От 1989 г. до 1992 г. за църквата са отговаряли свещенослужителите о. Захари Липчев, о. Любомир Димитров, о. Пламен Коларов, архим. Теофан, о. Александър Петров. На 17 Юли 1992 г. храмът се поема от о. Петко Минчев.
Днес в този си вид църквата "Св. Параскева" е възобновена с помощта на дарителската подкрепа и с усърдието на множество християни. От стария храм са запазени св. Престол и всички икони, както и каменните зидове, които са доукрепени. Сегашният иконостас е точно копие на стария. За шест месеца при събрани наполовина от необходимите средства, храмът е съборен и издигнат отново, при наличието на множество пречки и проблеми, както и недостиг на пари и материали. Построена е камбанария и предверие, като е постигната сполучлива адаптация в стилово отношение с околната архитектура. На 23 декември 2002 г. бе отслужена първата св. Литургия в обновената църква от Варненския и Великопреславски митрополит Кирил.
На 11 Ноември 2008 г. в храма бяха тържествено посрещнати ковчеже с частица от мощите на св. Параскева Римлянка дарени от митрополит Агатоник на Катерини (Гърция). Отново с дарителска подкрепа бяха намерени средства за направа на подходяща поставка (проскинитарий) за мощехранителницата. Днес мощите са изложени за поклонение на централно място в храма.
При изкопни работи през 2012 г. пред църквата са разкрити останки на античен храм от древния Одесос, което доказва тезата, че мястото, върху което е построена църквата, е сакрално от дълбока древност. Църквата отбелязва своя храмов празник на 26 юли.
Адрес на храм "Св. Параскева": гр. Варна ул. "Осми ноември" № 12