Ο ναός του Αγίου Νικολάου βρίσκεται ψηλά στη δυτική πλευρά της νησίδας. Διέθετε δύο θολοσκεπείς επιμήκεις χώρους (κλίτη) με τον νότιο να είναι μεγαλύτερο σε μήκος και ύψος από τον βόρειο, το οποίο φαίνεται να αποτελεί μεταγενέστερη προσθήκη. Είναι το μοναδικό κτίριο της νησίδας που χρονολογείται κατά τους πρώιμους χρόνους της Ενετικής περιόδου, πολύ πριν από τα ενετικά οχυρωματικά έργα.

Σήμερα σώζεται μόνο η ανατολική πλευρά τους. Στην αψίδα του νοτίου κλίτους υπάρχουν ίχνη τοιχογραφιών με παράσταση της Δέησης, δηλαδή του Χριστού πλαισιωμένου από την Παναγία και τον Ιωάννη τον Πρόδρομο, καθώς και με παράσταση του Ευαγγελισμού της Θεοτόκου, που χρονολογούνται τον 14ο αιώνα.

Ο ναός αποτελεί την πρώτη εκκλησία του φρουρίου της Σπιναλόγκας και κατά τη διάρκεια τη οικοδόμησης των οχυρώσεων χρησιμοποιείται από τους Ενετούς για να καλύψει τις άμεσες ανάγκες εκκλησιασμού της φρουράς. Για ένα διάστημα μάλιστα λειτουργεί και για τα δύο δόγματα, ενώ ανά διαστήματα χρησιμοποιείται και ως πυριτιδαποθήκη.