The Castle of Paramythia (“Castle of Saint Donatos”) is located northeast of the modern city, in a naturally fortified position (600m. altitude), which controls the natural pathways to the valleys of Acheron and Kalamas to the west and the passage from Eleftherohori to Dodona to the north.

The establishment of the first fortress dates back to the Hellenistic period. Part of this ancient fortification is preserved in the lower parts of the Byzantine and later castle. According to the historian Procopius, during the 6th cent. AD, Emperor Justinian I built a fortress named "St. Donatus", in the area of the ancient fortification, for the protection of the residents of the nearby town Fotiki. In the early 15th cent. the castle was the border of the Despotate of Epirus. After Paramythia’s fall to the Turks in 1430, the castle is mentioned in official documents as Aidonat Kalesi. The habitation continues until the beginning of the 19th cent., during the time of Ali Pasha of Ioannina, when it was finally abandoned.