Църквата „Света Параскева" се намира северно от главната улица на Стария Несебър, в непосредствена близост до църквата „Свети архангели Михаил и Гавраил“.

Старинната черква е изградена през XIII-XIV век. Църковната сграда е еднокорабна с размери 14,70 м дължина и 6,60 м ширина, и с характерен нартекс и олтарна апсида. На изток завършва с петстенна апсида. Градена е от дялан камък и от тухли, в редуващи се пояси.
Съвременният покрив е двускатен – наследство от по-късни векове. Църквата се е развивала във височина като типична кръстокуполна постройка – кръст, изразен в покрива и над него – в центъра – барабан с купол. Подобно на църквите „Христос Пантократор“ и „Свети архангели Михаил и Гавраил“ , над притвора се е издигала кула-звънарница, за която свидетелствува каменната стълба, вградена в зида, разделящ наоса от притвора. Покривната ѝ конструкция не се е съхранила. Предполага се, че е била куполна. Вероятно над нартекса е имало камбанария. Сегашният ѝ покрив е строен по-късно.
Украсата по фасадата е в керамопластичен стил, наподобаваща на тази на „Свети архангели Михаил и Гавраил“. По дължината на северната и южната фасада минава редица от слепи арки, чиито тимпани са богато орнаментирани. Мотивите – рибена кост, слънце, зигзаг, шахмат и др. са изпълнени от камък и тухли. Над тях в пояси се развива декоративна украса от четирилистни и кръгли глазирани панички, вградени в самата стенал
Църквата е реставрирана, но не напълно. През 2013 – 14 г. е частично възстановена по проект с работно заглавие „Реставрация, консервация, социализация на църквите „Св. Йоан Кръстител“, „Св. Параскева“ и прилежащото пространство“. Проектът е финансиран с европейски средства по оперативна програма „Регионално развитие“ (общата му стойност  е 1 643 230 лв, в това число собствен принос на община Несебър – 80 518 лв.). С въпросния проект е реализирана първата част от културно-историческия маршрут „Духовен път“, който е с дължина 320 м., а именно в участъка от „Св. Йоан Кръстител“ до църквите „Св. Параскева“ и „Св. архангели Михаил и Гавраил“.
Във възстановената църква е поместена галерия от ценни стенописни фрагменти, принадлежали на някои несъществуващи несебърски храмове (църквите „Св. Георги Стари (Големи)“, „Св. Климент“ и др.).



Използвана литература:
1. Рашенов, Александър. Месемврийски църкви. София, 1932 г
2. Мавродинов, Никола - Външната украса на старобългарските църкви, ИАИ, т. VIII, 1934 г.