Paxos war, so will es die Überlieferung, einst mit Kerkyra verbunden. Die häufigen Stürme, die Poseidon und Äolos entfachten, ließen die Erde nachgeben; seither bewegt sich Paxos ständig südwärts
Nach einer anderen, romantisch inspirierten Version, trennte Poseidon einst mit einem Wurf seiner dreizackigen Harpune Paxos von Kerkyra um sich auf diesem ruhigen Plätzchen ungestort dem Liebesspiel mit seiner Gefährtin Amphitrite hingeben zu können. Seither ist sein Dreizack das Emblem von Paxos.
Früheste Erwahnung Paxos in historischer Zeit finden wir bei Herodot, Plybios und Plutarch. 229 v.Chr. fand vor Paxos die Seeschlacht zwischen Kerkyraern und Illyriern statt, die zur Eroberung durch Rom fuhrte. 960 n.Chr. besuchte der Bischof Liutprand von Cremona die Insel und verfasste hier den dritten Band seiner Geschichte.
Bis 1380 n.Chr. (Epoche Anjous) folgte Paxos der geschichtlichen Entwicklung Korfus. Damals wurde Paxos an den Baron Adam San Ippolito abgetreten, und als sechs Jahre später die Venezianer Kerkyra eroberten, beließen sie ihn -nun als Lehensherrn- an seinem Platz. 1432 wurde die Festung auf der Ag.Nikolaus-Insel vor dem Hafen von Gaios zum Schutz der Insel vor Türken und Piraten gebaut. Nach dem Tod San Ippolitos heiratete seine Schwester und Erbin den Sizilianer Ricardo Altavilla und brachte die Insel in die Ehe ein. Von 1483 an kam Paxos fur 30 Jahre unter venezianische Gerichtsbarkeit der Familie Avrami. Die schwere Steuerlast unter diesen Herren der Insel und die ständig sich wiederholenden Überfalle von Piraten, was jeweils Plünderung und Verschleppung von Menschen in die Sklaverei bedeutete, brachten die Insel an den Rand der Verelendung. Olivenmonokultur und Entwicklung des Fernhandels durch staatlich organisierten Flottenbau sind die weiteren Hauptmerkmale der Venezianerherrschaft.
In der weiteren Geschichte losten sich die demokratischen Franzosen, die russisch-türkische Allianz, die Ionische Republik, dann wiederum Franzosen -diesmal die kaiserlichen- ab. 1810 kreuzte die britische Flotte im Ionischen Meer auf, besetzte Lefkas und bedrohte auch die übrigen unter Franzosenherrschaft stehenden Inseln. Paxos war in Aufruhr. Ausgehungert vom Getreidemangel und schwer unterdrückt von der autoritaren Herrschaft, erhob sich die Insel unter Anführung des Piraten Kapitan Kephalas. Die Aufstandischen hissten die englische Flagge, schlachteten die frankophilen Aristokraten ab, plünderten und brandschatzten ihre Hauser. Die Franzosen entsandten Truppen, zwangen die Revolte nieder, und brachten die Aufstandischen vor Kriegsgericht. 1811 wurden in Korfu unter den Angeklagten sieben Todesurteile vollstreckt; ihr Vermogen wurde beschlagnahmt.
Drei Jahre später landeten die Engländer unter der Führung des Griechen im Majorsrang, Theodoros Kolokotronis, und besetzten die Insel. In ihrer Zeit wurden Wasserversorgung, Strassen und Hafen gebaut und Schulen betrieben.
Seit sich 1864 die ionischen Inseln dem übrigen Griechenland anschlossen, folgt auch Paxos dem gemeinsamen neugriechischen Weg durch die Geschichte.