Νότια της εκκλησίας του Αγίου Νικολάου στα Κυριακοσέλια Αποκορώνου, πάνω στο λόφο του Καστελίου, βρίσκεται το ομώνυμο βυζαντινό κάστρο, λείψανα του οποίου σώζονται μέχρι σήμερα. Κτίστηκε από τον αυτοκράτορα Νικηφόρο Φωκά κατά τον 10ο αι., με στόχο να ελέγχει τη χερσαία είσοδο προς τον κόλπο της Σούδας. Φαίνεται ότι διέθετε ισχυρή οχύρωση και έφερε μία μονάχα είσοδο προς τα δυτικά. Όταν το κατέλαβαν οι Ενετοί, εξακολούθησαν να το χρησιμοποιούν ως οχυρό παρατηρητήριο, ονομάζοντας το Rocca di San Nicolo. Στο εσωτερικό του υπήρχε ο βυζαντινός ναός της Αγίας Παρασκευής, στα ερείπια της οποίας κτίστηκε αργότερα νεώτερος ναός προς τιμήν της ίδιας Αγίας.