Η μυθολογία θέλει τους Παξούς να δημιουργούνται όταν ο Ποσειδώνας, ο θεός της θάλασσας, χτύπησε με την τρίαινά του την Κέρκυρα κόβοντάς της ένα κομμάτι. Αυτό το κομμάτι είναι σήμερα οι Παξοί. Μάλιστα οι κάτοικοι θέλοντας να επιδοκιμάσουν αυτή την εκδοχή έχουν υιοθετήσει σαν σύμβολο του νησιού την τρίαινα.

Η μοίρα των Παξών είναι σχεδόν άρρηκτα συνδεδεμένη με την Κέρκυρα. Το 1386 η Βενετία κατακτά τα Επτάνησα και οι Παξοί αποτελούν τιμάριο που παραχωρείται σε Ενετούς ευγενείς.
Το 1537 ο ενετικός στόλος συναντάει τον τουρκικό έξω από τους Παξούς και ξεκινάει μια μεγάλη ναυμαχία που καταλήγει σε συντριπτική ήττα των Τούρκων. Η θάλασσα δεν σταματά να ξεβράζει πτώματα στους Παξούς και οι Τούρκοι ορκίζονται εκδίκηση. Η εκδίκηση έχει όνομα. Μπαρμπαρόσα. Ο διαβόητος πειρατής επιτίθεται στην Κέρκυρα και την πολιορκεί, όμως το νησί αντιστέκεται σθεναρά. Τότε ο Μπαρμπαρόσα αποσύρεται απογοητευμένος και, για να μην επιστρέψει ταπεινωμένος, στρέφεται εναντίον των Παξών και τους λεηλατεί σφάζοντας και ουσιαστικά ερημώνοντας το νησί. Όσοι γλύτωσαν από αυτή την επιδρομή θα γνωρίσουν μια νέα, εξίσου άγρια το 1571.

Το 1821 οι Παξοί υψώνουν τη σημαία της ελληνικής επανάστασης. Μάλιστα από τους Παξούς καταγόταν ο ηρωικός πυρπολητής Γεώργιος Ανεμογιάννης, το άγαλμα του οποίου κοσμεί το λιμάνι της Ναυπάκτου. Το 1864 μαζί με τα υπόλοιπα Επτάνησα οι Παξοί ενσωματώνονται στο ελληνικό κράτος.