Γεννήθηκε στις 19 Ιουνίου του 1911, ημέρα Κυριακή, ώρα τρεις το απόγευμα, όπως του άρεσε να διευκρινίζει. Ρεθυμνιώτης γέννημα - θρέμμα. Στέλιος Φουσταλιεράκης του Στυλιανού και της Κυριακούλας. Του δώσανε, το όνομα του πατέρα του που σκοτώθηκε σε ατύχημα όταν η μάνα του ήταν πέντε μηνών έγκυος. Δεκαεννιά χρονών ήταν, σαν χάθηκε κι η μάνα του δεκάξι, έξι μηνών νιόνυφη. Έτσι ο Στέλιος μπήκε στην περιπέτεια της ζωής πριν ακόμη γεννηθεί! Πηγαίνοντας στο νυχτερινό σχολείο, ως την τρίτη δημοτικού στα 11 χρόνια του αρχίζει να μυείται στην τέχνη του ρολογά - το δεύτερο μεγάλο πάθος του, μετά το μπουλγάρι. Δύο χρόνια αργότερα, παραμονή πρωτοχρονιάς, ο μικρός Στέλιος παίρνει την πρώτη του πληρωμή, ένα ολόκληρο κατοστάρικο. Και ξέρει ήδη από τα πριν που θα το διαθέσει!....
Με την μεσολάβηση του πατριού του και 75 δραχμές αποκτά το πρώτο του μπουλγάρι. Το μπουλγάρι ασκούσε μια ιδιαίτερη γοητεία πάνω του. Και δεν ήταν μόνο επειδή ο αδελφός της μητέρας του - ο Γιώργος Κανελλάκης - έπαιζε αυτό το όργανο. «Την εποχή αυτή το Ρέθυμνο ήταν γεμάτο από μπουλγάρια. Κάθε ταβέρνα είχε κι από ένα. Εκεί πήρα τα πρώτα μου ακούσματα. Έβλεπα τους άλλους που παίζανε και - στο λόγο της αντρικής μου τιμής - έκλαιγα!...». Τότε «βοηθοί» (όργανα συνοδείας) της λύρας ήταν κυρίως το μπουλγάρι και το μαντολίνο. Το λαούτο ο Φουσταλιέρης το θυμάται στην εποχή του Ρεθύμνου μετά το 1930, με το Σταύρο Ψυλλάκη - Ψύλλο από την Επισκοπή. Έτσι το Αντώνης Καρεκλάς ονομαστός ήδη λυράρης της εποχής του, είχε για συνοδούς στο μπουλγάρι τον Γιώργη Αγιούτη ή τον Βλαδίμηρο. Σ' αυτούς ήρθε να προστεθεί, αρχάριος ακόμη, ο Φουσταλιέρης που ήταν ανιψιός του ( ο Καρεκλάς είχε παντρευτεί την αδελφή της μητέρας του). "Όσο μεγάλωνα τόσο έμπαινα στον νταλκά του οργάνου", θυμάται. Δύο χρόνια αργότερα, έχοντας μάθει πολλά κοντά στον Καρεκλά, αρχίζει να πηγαίνει μαζί του σε γάμους και σε γλέντια και να τον συνοδεύει ως "πασαδόρος."
"Στα χωριά ζητούσαν τότε χωραϊτικα όργανα, από το Ρέθυμνο δηλαδή. Όμως οι γάμοι ήταν σκληροί, ζόρικοι. Με τα δάχτυλα μετρούσα το πότε είχα κοιμηθεί στο σπίτι μου. Το γαμήλιο γλέντι κρατούσε 5 - 6 νύκτες. Στα Σφακιά έφτανε και τις 15!... Εγώ ήμουνα χλωμός από τα ξενύχτια, τα δάχτυλα μου πρήζονταν και τα νύχια μου σκιζόταν. Έπαιζα και μ' έπαιρνε ο ύπνος πάνω στο όργανο. Ο Καρεκλάς τότε - που είχε την μεγαλύτερη αντοχή απ' όλους μας - μου έπαιζε μια με το πόδι του, ξυπνούσα και συνέχιζα... Κι από λεφτά λίγα πράγματα. Ο κόσμος τότε ήταν φτωχός. Με τη βία βγάζαμε σε κάθε γάμο τρία ως οχτώ κατοστάρικα, όλοι μαζί. Ήταν σαν χαρτζιλίκι. Που τα λεφτά που παίρνουν οι σημερινοί! Και μετά περιμέναμε κανένα κάρο για να μας γυρίσει το στο Ρέθυμνο!...». 
Έτσι με τα πρώτα ακούσματα από τις ταβέρνες του Ρεθύμνου και τη συνεργασία του με τον Καρεκλά ο Φουσταλιέρης αρχίζει σιγά - σιγά να παίζει απ' όλα: συρτό, πεντοζάλια, πηδηχτά, καστρινά, ταξίμια, καθιστικά, "αχόρευτα, της ταβέρνας, της παρέας" ακόμα και ρεμπέτικα. Αν και κρατούσε πάντα την τέχνη του ρολογά και δεν υπήρξε ποτέ επαγγελματίας οργανοπαίκτης, ο δεξιοτεχνίτης που είχε ξυπνήσει μέσα του δεν μπορούσε να ικανοποιηθεί "κρατώντας μόνο το μπάσο του λυρατζή".  Ο Καρεκλάς που εκτιμούσε το ταλέντο του το καταλάβαινε αυτό και συχνά "αλάφρωνε το δοξάρι και άνοιγε δρόμο για να περνάω εγώ μπροστά. Σιγά - σιγά πήρα δρόμο, πετάχτηκα, έφυγα, απομακρύνθηκα από τη λύρα κι έκανα δικιά μου κυβέρνηση, δικό μου συγκρότημα!...". Ο Φουσταλιέρης δημιουργεί λοιπόν τη δική του «σχολή» στο χώρο της Κρητικής μουσικής, αναδεικνύοντας το μπουλγάρι σε όργανο μελωδικό και σολιστικό, με αποκορύφωμα στην είσοδο και καθιέρωση του στο χώρο της δισκογραφίας των 78 στροφών.
Εκτός από τον Καρεκλά συνεργάστηκε και με άλλους λυράρηδες, τον Σοφοκλή Παπατζανή, τον Γιώργο Πατεράκη (από τον Πρινέ), και τον Γιάννη Γελούντα. Στη δισκογραφία χρησιμοποίησε επίσης τον Κώστα Καρύπη, το Στέλιο Χρυσίνη, και τον Βαγγέλη Φραγκιαδάκη (που κρατούσαν το μπάσο με την κιθάρα) και τον Νταβά με τη μαντόλα για σεκόντο. Παράλληλα στις Ρεθεμνιώτικες συντροφιές έπαιζε συχνά με μικρασιάτες μουσικούς που είχαν έρθει εδώ μετά την καταστροφή. Αναφέρεται λοιπόν μια κομπανία που την αποτελούσαν ο Καρεκλάς (λύρα), ο Φουσταλιέρης (μπουλγάρι), ο Γιάννης ο Αρμένης (ούτι), κι ο Μιχαλάκης Αραμπατζόγλου (σαντούρι).  Δυστυχώς, δεν διασώθηκαν ηχογραφήσεις τους. Από τους τραγουδιστές η πιο γόνιμη συνεργασία του υπήρξε με τον Ρεθυμνιώτη Γιάννη Μπερνιδάκη (1910 - 1972), τον "Μπαξεβάνη", όπως έμεινε γνωστός εξαιτίας του τραγουδιού του που το παρομοίασαν με περιβόλι. Σχεδόν συνομήλικος με το Φουσταλιέρη, ο Μπαξεβάνης τραγούδησε στη δισκογραφία τα περισσότερα από τα τραγούδια που διεκδικεί την πατρότητά τους ο Φουσταλιέρης και που έγιναν επιτυχίες: "Όσο βαρούν τα σίδερα" και το "Μερακλίδικο πουλί" (1937), "Τα βάσανα μου χαίρομαι" (1938), "Πονεμένη καρδιά" (1940) κ.α. Με τον Φουσταλιέρη συνεργάστηκε επίσης και η αδελφή του Μπαξεβάνη, η Λαυρεντία Μπερνιδάκη, η πρώτη γυναίκα που τραγούδησε στη δισκογραφία της Κρητικής μουσικής ("Συρτός πρώτος" και "Κοντυλιές Μυλοποταμίτικες"), με φωνητικά προσόντα εφάμιλλα του αδελφού της. Επίσης συνόδεψε με το μπουλγάρι του σε δικές του συνθέσεις το Γιώργο Τζιμάκη ("Σαν δεις αγάπης δάκρυα", "Στ' αραχνιασμένο μνήμα μου", - μετά τον πόλεμο) καθώς και τον Θεοχάρη Ζωγράφο ("Κρητικοπούλα") ενώ σε ορισμένες ηχογραφήσεις δεύτερη φωνή στον Μπαξεβάνη έκανε ο Στελλάκης Περπινιάδης. Στο στούντιο της Ριζούπολης με ηχολήπτη τον Αρεταίο και υπεύθυνο για το ρεπερτόριο τον Παναγιώτη Τούντα, ο Φουσταλιέρης "χτύπησε" συνολικά είκοσι τέσσερις δίσκους. Πρωτόγονες οι συνθήκες της ηχογράφησης (σε ισπανικό κερί) αλλά και επικίνδυνοι οι καιροί με τη λογοκρισία της Μεταξικής δικτατορίας, που απειλούσε στίχους και μουσική με την κόκκινη σφραγίδα του "Υφυπουργείου Τύπου και Τουρισμού". Ιδιαίτερα σημαντικό για την διαμόρφωση της μουσικής προσωπικότητάς του Φουσταλιέρη υπήρξε το διάστημα της παραμονής του στον Πειραιά (1933 - 1937). Εδώ η παραδοσιακή Κρητική μουσική συναντά το ρεύμα του ρεμπέτικου, καθώς ο Στέλιος συναντιέται μ' όλα τα μεγάλα ονόματα: Γιώργος Μπάτης, Μάρκος Βαμβακάρης, Γιάννης Παπαϊωάννου, Στράτος Παγιουμτζής, Κερομύτης Μπαγιαντέρας. Παλιός γνώριμος με τον Μπατή (από τον καιρό που αυτός είχε πάει στο Ρέθυμνο, ως...βοηθός πλανόδιου οδοντίατρου!), συχνάζει στην "παράγκα" του στην πλατεία Καραϊσκάκη. Εδώ ήταν κρεμασμένα στην σειρά τα μπουζούκια, έχοντας το καθένα το όνομά του, η Μαριγούλη, η Κούλα, η Γυφτοπούλα, η τσιγγάνα, ο γέρο - μάγκας ( ο τζούρας) κλπ. Ανάμεσα σ' αυτά και το μπουλγάρι που παίζει το "Στελλάκι από την Κρήτη" κι ενθουσιάζει τους ρεμπέτες με τη "διπλοπενιά" και την "τριπλοπενιά" του.
Από το 1937 έως το 1992 που πέθανε, ο Στέλιος Φουσταλιεράκης ζούσε στο Ρέθυμνο συνδυάζοντας πάντοτε τις δύο μεγάλες του αγάπες του: την τέχνη του ρολογά και το μπουλγάρι : "Γιατί και οι δύο αυτές τέχνες έχουν μεγάλη σχέση μεταξύ τους, είναι λεπτή δουλειά. Όπως παλιά κάναμε τα εξαρτήματα των ρολογιών στο χέρι και δουλεύαμε με το φακό, έτσι και στη μουσική χρειάζεται σημασία στη λεπτομέρεια, στην πενιά. Χρειάζεται αξιοπρέπεια τόσο πίσω από τον πάγκο όσο και όταν παίζω όργανο". Ο Φουσταλιέρης με την ίδια αξιοπρέπεια και το ίδιο αμείωτο μεράκι παρέμεινε ως το θάνατό του, όχι μόνο στην Κρήτη αλλά και σ' ολόκληρη την Ελλάδα, ένας από τους τελευταίους εκπροσώπους της παράδοσης του Ελληνικού ταμπουρά.
Γιατί , δυστυχώς, στις μέρες μας η μακραίωνη αυτή παράδοση κινδυνεύει να εξαφανιστεί. Το λαγούτα και το μπουζούκι εκτόπισαν το μπουλγάρι, όπως τα ηλεκτρονικά ρολόγια τους παλαιότερους τύπους ρολογιών. Η ζωή συνεχίζεται σε μια Ελλάδα, όπου ολοένα αυξάνονται οι δυτικές και αστικές επιδράσεις, σπρώχνοντας στο περιθώριο πολλά στοιχεία της παλαιάς παράδοσης. Όμως τουλάχιστον απ' αυλάκια των παλιών αυτών δίσκων, έχουν διασωθεί τα δείγματα της τέχνης του Φουσταλιέρη. Μιας τέχνης που γεφυρώνει την δημοτική με την αστική μουσική της Κρήτης κι ενώνει - μ' ένα τρόπο τρίγωνο - την Κρητική με την μικρασιατική και τη ρεμπέτικη. Μιας τέχνης που αν και είναι προσωπική (αποτέλεσμα του ταλέντου και της προσωπικότητας ενός επώνυμου δημιουργού) εντάσσεται και λειτουργεί αποτελεσματικά μέσα στο σύνολο, επειδή ακριβώς πατάει γερά στην κοινή μουσική κληρονομιά και τα κοινά βιώματα του Κρητικού λαού. 
Γι' αυτό η μουσική του Φουσταλιέρη αποτελεί ένα ξεχωριστό και ιδιαίτερα σημαντικό κεφάλαιο στην ιστορία της Κρητικής μουσικής...