Ο προμαχώνας Αγίου Ανδρέα στην αρχή ονομάστηκε προμαχώνας του Αγίου Πνεύματος από την ομώνυμη μικρή εκκλησία που βρισκόταν στην εξωτερική πλευρά της οχύρωσης. Το 17ο αι. επικράτησε να λέγεται προμαχώνας Αγίου Ανδρέα από την εκκλησία που βρισκόταν στο εσωτερικό της οχύρωσης.
Από την ενετική κατασκευή σώζεται μόνο η χάραξη του ίχνους της νότιας πλευράς της χαμηλής πλατείας. Ο ενετικός προμαχώνας είχε ένα μόνο ημικυκλικό τμήμα και μια χαμηλή πλατεία προς το νότο. Η βόρεια πλευρά του ήταν ευθύγραμμη και σ' αυτήν ανοιγόταν μια πύλη.
Οι Τούρκοι ανακατασκεύασαν ολόκληρο τον προμαχώνα και του έδωσαν νέα καρδιόσχημη μορφή. Ο επιπρομαχώνας που σώζεται σήμερα είναι επίσης τουρκικής κατασκευής.
Σήμερα ο χώρος του προμαχώνα έχει διαμορφωθεί σε χώρο περιπάτου και ξεκούρασης. Ένα δρομάκι ξεκινάει από εδώ και φτάνει μέχρι τον προμαχώνα Μαρτινέγκο.