Blisko centrum wznosi się cerkiew św. Paraskewy posiadająca jedną nawę i pięciokątną apsydę oraz bogaty wystrój zewnętrzny. Jej kopuła i dzwonnica nie zostały zachowane do dzisiaj i nie wiadomo, której z trzech świętych o nazwie Paraskewa, cerkiew została poświęcona. Data powstania kościoła św. Paraskewy jest kwestią nie rozstrzygniętą do dzisiaj. Chociaż niektórzy badacze twierdzą, iż powstała w X wieku, to ogólnie przyjmuje się, że została zbudowana na przełomie wieków XIII- XIV. Ocena ta opiera się na jej architektonicznych podobieństwach do kościołów z tego okresu średniowiecznej stolicy Bułgarii Wielkie Tyrnowo. Obecnie nabożeństwa się tutaj nie odbywają, ponieważ świątynia pełni funkcję galerii sztuki.

Jest to jednonawowa budowla, zbudowana na planie krzyża bizantyjskiego. Posiada babiniec w zachodniej części i jedne szerokie pięciokątne prezbiterium we wschodniej części. Kościół został zbudowany z cegieł i wygładzonych kamieni. W przeszłości kościół miał kopułę, a dwuspadowym dachem został nakryty w czasach najnowszych. Podobnie jak inne kościoły w Nesebyrze datowane na ten sam okres, kościół św. Paraskewy został bogato ozdobiony na zewnątrz. Dwa rzędy po osiem wąskich łuków każdy dekorują północną i południową ścianę. Widoczne są także zdobienia z kolorowych ceramicznych rozet.

Zdjęcia wykonano w lipcu 2016 roku.