Ο Άγιος Νικόλαος είναι ο πολιούχος του παραδοσιακού χωριού Τύλισος, το οποίο απέχει 14 χιλιόμετρα από το Ηράκλειο.
Ο ναός είναι κτισμένος στα τέλη του 19ου αιώνα στη θέση ενός μοναστηριού που υπήρχε εκεί επί ενετοκρατίας ονοματισμένος στον ίδιο Άγιο.
Ο υφιστάμενος ναός κτίστηκε μετά το 1850 , στο τέμπλο του αναγράφεται 1866.
Το σήμαντρο της καμπάνας του Αγίου Νικολάου ήχησε για πρώτη φορά στις 5 Δεκεμβρίου του 1887. Μάλιστα, σύμφωνα με μαρτυρίες, ακούστηκε μέχρι το Γάζι.
Ο ναός είναι δίκλιτος και και το δεύτερο κλίτος είναι αφιερωμένο στον Άγιο Γεώργιο, πανηγυρίζει στις 6 Δεκεμβρίου και την ημέρα αυτή σερβίρεται βακαλάος τηγανητός με σκορδαλιά.
Η γιορτή του μπακαλιάρου έχει καθιερωθεί τα τελευταία δέκα χρόνια.
Οι Τυλισσανοί όμως ονομάζονταν ήδη μπακαλιάροι γιατί στα παλιά χρόνια όταν κατέβαιναν στη χώρα-Ηράκλειο- για να πουλήσουν τα αχινοπόδια και τα ξύλα που μάζευαν, συνήθιζαν ερχόμενοι να αγοράζουν το λεγόμενο φτυάρι μπακαλιάρου.
γνωρίζοντας αυτή τη συνήθεια τους οι κάτοικοι των γύρω χωριών τους έδψσαν την ονομασία "Μπακαλιάροι".
Έτσι, καθιερώθηκε σιγά, σιγά και κάθε παραμονή γιορτής του Αγίου Νικολάου, πολιούχου του χωριού, οι κάτοικοι δίνουν ένα κέρασμα με μπακαλιάρο στους προσκυνητές.
