Στον κατάλογο 5 των εκκλησιών του Ηρακλείου (G. Gerola, Topografia delle chiese della citta di Candia), που συντάχθηκε μετά το 1600 από τον παπά κυρ. Ιωάννη Κομητά, αναφέρεται ως Άγιος Ματθαίος του Μάρκου Φεουτέου. Σύμφωνα με επιγραφή, που είναι εντοιχισμένη πάνω από τη νότια είσοδο, κτίστηκε το 1600. Από νοταριακές πηγές γνωρίζουμε ότι η εκκλησία είχε κτιστεί με «κόπο και σπέζα» του Μάστρο Νικολό Κουδουμνή μέσα στο περιβόλι που είχε στην ενορία του Αγίου Γεωργίου Συριανού. Ανήκε στη συντεχνία των φουρνάρηδων.