Ο μύθος θέλει τους Παξούς να είναι δημιούργημα του έρωτα του Ποσειδώνα γιὰ τὴν Αμφιτρίτη, όταν τους απέκοψε από την Κέρκυρα, θέλοντας να έχει μια ερωτική φωλιά για τους δυο τους.

Δεν υπάρχουν ντοκουμέντα και πηγές αξιόπιστες για το απώτατο παρελθόν των νησιών, αλλά φαίνεται ότι, όπως και τα άλλα νησιά των Επτανήσων, μετά τους πρώτους προέλληνες κατοίκους τους, εποικίσθηκαν από ελληνικά φύλα της Ηπείρου.

Από τον 3ο αι. π.Χ. οι Παξοί έγιναν ρωμαϊκό έδαφος και σαν τέτοιο διήνυσαν όλην την περίοδο της Υστερης Αρχαιότητας και του Μεσαίωνα. Από τον 14ο αι. οι Παξοί ήταν ενετική κτίση. Τον 16ο αι. το νησί καταστράφηκε ολοσχερώς από τον τουρκικό στόλο και οι επιζήσαντες το εγκατέλειψαν και μετοίκισαν στους Οθωνούς.

Οι Παξοί ακολούθησαν την μοίρα της Κέρκυρας, μέχρι το 1814, όταν Θεόδωρος Κολοκοτρώνης, με αγγλικές δυνάμεις, αποβιβάστηκε στην Λάκκα και κατέλαβε το Κάστρο του Αη Νικόλα στον Γάϊο. Κατά την διάρκεια της Επανάστασης του 1821 οι Παξινοί συμμετείχαν στον αγώνα. Στην Ναύπακτο, ο νεαρός Παξινός μπουρλοτιέρης Γεώργιος Ανεμογιάννης βρήκε τραγικό θάνατο στα χέρια των Τούρκων βασανιστών του. Το 1864 ενώθηκαν με την Ελλάδα μαζί με τα υπόλοιπα Επτάνησα.