Le plateau de la colline de Paliokastro, sur lequel se trouvait le noyau de la ville, était protégé par une muraille de 3 480 m de long. Le plateau, situé à 231 m d’altitude, est une forteresse naturelle stratégiquement située, avec des pentes abruptes et peu de points d’accès. Les fortifications sont antérieures au milieu du IVe siècle avant J.-C., comme en témoignent leur construction et les poteries trouvées dans les tranchées d’essai creusées dans la couche de fondation du côté ouest. Suivant et exploitant le terrain, qui imposait une approche différente pour chaque section afin d’assurer de meilleures défenses et d’éviter le gaspillage des ressources, les fortifications ne sont pas construites selon une conception architecturale unifiée. Le plan au sol présente des crêtes qui étaient très utiles pour la défense. Les points faibles étaient protégés par des tours (six ont été trouvées à ce jour).

La construction et la largeur du mur varient, de même que la forme et l’espacement des tours. La maçonnerie exploite également le terrain. Les rochers des côtés sud et sud-est constituaient des défenses naturelles. Les fortifications des côtés nord et nord-est, où la colline est abrupte, sont construites avec de grosses pierres de taille inégale. Sur le côté est, où le terrain est plus accidenté, un système polygonal mixte est utilisé, avec des pierres de taille rectangulaires entrecoupées de blocs plus irréguliers. Sur les côtés ouest et sud-ouest, où se trouvait la porte principale, la maçonnerie est plus élaborée, avec des pierres de taille rectangulaires aux faces rugueuses et incurvées et des joints profonds dans le système pseudo-isodomique. Ce côté présente également des sections de maçonnerie pseudo-isodomique encore plus soignées, composées de pierres de taille à faces lisses.

Sur le côté ouest des fortifications, plus accessible, se trouvent trois portes, deux au sud-ouest et une au nord-ouest. L’une d’entre elles est la porte principale, la plus élaborée. Accessible par une route pavée, elle est protégée par une tour rectangulaire à l’ouest. Une autre porte du côté nord-est, avec des montants monolithiques bien conservés, est connue sous le nom de « Porte de fer » (Sideroporti). De là, une route pavée descendait vers le port de Kissamos, les villes et villages périphériques de la vallée (aujourd’hui Kalámi et Kyani Akti) et d’autres villes à l’est. Il y avait des poternes à intervalles réguliers, comme on peut le voir sur le mur ouest.

Les fortifications d’Aptera sont du type avancé du IVe siècle avant J.-C., largement adopté en Crète à cette époque, et comprennent des défenses destinées à résister aux nouveaux engins de siège. Elles sont dotées de poternes, de murs transversaux et de tours carrées à plusieurs étages où étaient placées les machines de guerre. De nombreux vestiges d’un siège à l’époque hellénistique (tir de catapulte, balles et moules de fronde, pointes de lance et de flèche) ont été découverts lors des fouilles sur le côté ouest du mur, en particulier près de la tour. Nous savons que la ville a été assiégée par la Polyrrhénie et ses alliés, Philippe V de Macédoine et les Achéens, pendant la grande guerre de Crète de 220 av. J.-C. (Polybe ΙV, 55,4).

Des maçonneries en pierre de taille aussi méticuleuses sont également présentes dans d’autres fortifications crétoises de l’époque, à Eléftherna, Phaistos, Phalassarna, Mátala, Kastrí dans Keratókambos et Viánnos. La maçonnerie polygonale est également présente à Hyrtakina.