Η σημερινή πόλη του Αγίου Νικολάου έχει αναπτυχθεί πάνω στα ίχνη της αρχαίας πόλης "Λατούς προς Καμάρα", που ήταν το λιμάνι της "Λατούς Ετέρας" (Λατώ). Η μεγάλη αυτή Δωρική πόλη, ήταν χτισμένη πάνω σε προγενέστερη Μινωική θέση και ήταν η ιδιαίτερη πατρίδα του Νεάρχου, Ναυάρχου του Μ. Αλεξάνδρου.
Μετά τη Βυζαντινή περίοδο, στα χρόνια της Ενετοκρατίας (1204-1669), χτίστηκε από Γενοβέζους πειρατές το φρούριο "Μιρα-μπέλλο" (ωραία θέση) και από αυτό πήρε το όνομα της όλη η επαρχία. Το φρούριο αυτό δεν υπάρχει σήμερα. Η πόλη μάλλον παρήκμασε στα χρόνια της Τουρκοκρατίας. Το 1881 ήταν μόνο ένα μικρό χωριό με ελάχιστους κατοίκους, αλλά μέχρι το 1905 αναπτύχθηκε ξανά και έγινε πρωτεύουσα του Νομού Λασιθίου. Το σημερινό της όνομα, το πήρε από τη μικρή Βυζαντινή εκκλησία του Αη Νικόλα , που χτίστηκε τον 7ο αιώνα στη θέση "Νησί". Διασώζονται σ' αυτό παμπάλαιες τοιχογραφίες του 8ου, 10ου και 11ου αιώνα.
