Το όνομα της Φολεγάνδρου αποδίδεται από τη μυθολογία σε έναν γιο του βασιλιά της Κρήτης Μίνωα, τον Φολέγανδρο, που θεωρήθηκε πρώτος οικιστής του νησιού· άλλη εκδοχή συνδέει το όνομα με τη φοινικική λέξη για το βραχώδες, πετρώδες έδαφος. Ίχνη κατοίκησης ανάγονται στην προϊστορική εποχή, ενώ το άγριο, οχυρό τοπίο σφράγισε από νωρίς τη μοίρα του νησιού.
Στην αρχαιότητα η Φολέγανδρος κατοικήθηκε από Δωριείς και αργότερα εντάχθηκε στην αθηναϊκή επιρροή. Λόγω της απομόνωσης και της τραχύτητάς της, οι Ρωμαίοι τη χρησιμοποίησαν ως τόπο εξορίας — μια χρήση που επανήλθε και σε νεότερους χρόνους. Στη Χρυσοσπηλιά, αρχαίες επιγραφές μαρτυρούν λατρευτική δραστηριότητα ήδη από τα κλασικά χρόνια.
Στα βυζαντινά και μεσαιωνικά χρόνια το νησί υπέφερε από τις επιδρομές των πειρατών. Μετά την Δ΄ Σταυροφορία, το 1207, πέρασε στους Βενετούς και εντάχθηκε στο Δουκάτο του Αιγαίου του Μάρκου Σανούδου· τότε οχυρώθηκε ο οικισμός του Κάστρου στην άκρη του γκρεμού, με τα σπίτια να σχηματίζουν συνεχές τείχος για προστασία.
Το 1566 η Φολέγανδρος πέρασε στην Οθωμανική Αυτοκρατορία, συνεχίζοντας να δοκιμάζεται από πειρατικές επιδρομές έως τον 18ο αιώνα. Ενσωματώθηκε στο ελληνικό κράτος μετά την Επανάσταση του 1821, ενώ τον 20ό αιώνα χρησιμοποιήθηκε ξανά ως τόπος εξορίας. Χάρη στον μετρημένο, ήπιο τουρισμό των τελευταίων δεκαετιών, το νησί διατήρησε ανέγγιχτο τον αυθεντικό, γαλήνιο χαρακτήρα του.