The Basilica is located 2 km southwest from Stobi, opposite of the village of Palikura. It was discovered and excavated in1916 by the German soldiers. New excavations were undertaken in 1954, 1970 and 1980.
It has three aisles and a narthex. The aisles are separated by colonnades with five columns. The columns and the capitals belonged to some older buildings and they were reused in the construction of the church. To the east of the building there are four connected rooms. One of them has an octagonal plan, which leads some scholars to assume that this is a baptistery while others believe it was a martirium.
The Palikura Basilica was built on the road to Heraclea Lyncestis. Because of the isolated position and the rooms at the east side the whole complex is thought to be a monastery. The chronology of the construction is unclear but is put in the frames between the end of the 5th and the beginning of the 6th century AD.
During the Late Antiquity and the Middle Ages the area around the church served as a cemetery.