Church has been dedicated to St. Paraskeva (Petka) Epivatska of Bulgaria, whose holy remains were transported to the old capital city Tarnovo in 1238 and are currently in the Romanian city Iasi. According to the preserved inscription it was built in the period 1241-1257. It was most probably a court church of the governor of Sofia at the time – sebastokrator Kaloyan. It was built on the remains of the castle of Constantine I the Great.

In 1930 the church was incorporated into the new building of the Sofia bishopric.
The holy possessions of the church are a couple of miracle-working icons, the tree of Holy Martyr Therapon and the Holy Spring of St. Petka.