Λίγα μέτρα μακριά από το κέντρο της πόλης του Ηρακλείου, σε ένα μικρό ύψωμα, βρίσκεται το δημοτικό κοιμητήριο του Αγίου Κωνσταντίνου και Ελένης, που πήρε το όνομά του από την ομώνυμη εκκλησία. Ο επιβλητικός Ιερός Ναός Αγίου Κωνσταντίνου και Ελένης δεσπόζει στο κέντρο του κοιμητηρίου και εντυπωσιάζει τόσο με την αρχιτεκτονική του όσο και την ιστορία του.

Το «Νέον Χριστιανικόν Κοιμητήριον» του Ηρακλείου, που ήταν και το πρώτο συγκροτημένο κοιμητήριο της πόλης, ιδρύθηκε περίπου το 1893. Λίγα χρόνια αργότερα, στις 25 Μαΐου του 1985 ολοκληρώνονται και οι οικοδομικές εργασίες της εκκλησίας των Αγίων. Ο αρχιτεκτονικός διάκοσμος του ναού περιλαμβάνει περίτεχνα παράθυρα και πολύχρωμα βιτρό, ενώ οι εναλλαγές του κίτρινου και του λευκού χρώματος έρχονται σε πλήρη αρμονία με το φυσικό περιβάλλον. Εσωτερικά η εκκλησία κοσμείται από τις αγιογραφίες και τις εικόνες των Αγίων, με το ιερό να κεντρίζει το ενδιαφέρον του επισκέπτη με τη λαμπρότητά του. Ο μεγάλος αύλειος χώρος σε συνδυασμό με τις ξύλινες πέργκολες και τα καθίσματα, προσφέρουν ένα μέρος ανάπαυλας και περισυλλογής.

Ο Ιερός Ναός του Αγίου Κωνσταντίνου και Ελένης κουβαλά πολλές ιστορίες ανθρώπων, ανάμεσά τους και ο πρώτος γάμος του μεγάλου Κρητικού συγγραφέα Νίκου Καζαντζάκη με την Γαλάτεια Αλεξίου το 1911. Το ζευγάρι παντρεύτηκε μυστικά στον Ιερό Ναό με την παρουσία λίγων φίλων και του κουμπάρου τους, συμφοιτητή και στενού φίλου του Καζαντζάκη, του δικηγόρου Γεωργίου Φανουράκη.