Το χωριό Στόλοι βρίσκεται στα νότια του νομού Ηρακλείου, σε υψόμετρο 280 μέτρα και απέχει περίπου 56 χιλιόμετρα από τη πόλη του Ηρακλείου. Οι κάτοικοι του που σύμφωνα με την απογραφή του 2011 αριθμούν τους 345 ασχολούνται με την κτηνοτροφία και γεωργία.

Η ονομασία του χωριού προέρχεται από τους Αγίους Αποστόλους, την εκκλησία που προϋπήρχε στη θέση του σημερινού νεκροταφείου. Αρχικά αναφέρεται για πρώτη φορά σε έγραφα του Ενετού Fr. Barozzi το 1577 με την ονομασία Stolus. Κατά την πρώτη τούρκικη απογραφή του 1671 το χωριό δεν αναφέρεται, ενώ αργότερα μέχρι και το 1894 αναφέρεται μόνο με μουλσουμανικές οικογένειες. Έπειτα από την ανταλλαγή πληθυσμών εγκαθίστανται στο χωριό πρόσφυγες και ορισμένες οικογένειες Κρητικών και αναφέρεται το χωρίο στην απογραφή του 1900 με 56 κατοίκους.