Podle řecké mytologie se traduje, že na ostrově Naxos byl vychován Zeus, vládce bohů a lidí. Na tomto ostrově zanechal Théseus Ariadnu, dceru krále Mínoa. Ta se do řeckého hrdiny zamilovala. Pomohla mu přemoci Minotaura a dostat se z knósského labyrintu. Théseus ji ale na ostrově opustil, jelikož se zamiloval do její mladší sestry Faidry. Ariadna Théseovu zradu neunesla a spáchala sebevraždu. Podle jiné verze se ale stala manželkou boha vína Dionýsa, patrona ostrova Naxos. Na motivy tohoto mýtu vznikla opera Richarda Strausse Ariadna z Naxu.
Chrám bohyně Démétér na ostrově Naxos
První starověcí historičtí obyvatelé ostrova byli orientální Kárové a již v neolitu zde byla vyspělá kultura. Vládcem ostrova byl podle legendy karský král Naxos, podle kterého nese ostrov své jméno.
Okolo roku 1300 před naším letopočtem se na ostrově usazují řecké kmeny Achájců a ostrov se stal součástí mykénské kultury. Koncem druhého tisíciletí před naším letopočtem se tu usadili řečtí Iónové, ale je možné, že zde žili již od mykénské doby.
V klasickém období byl Naxos iónským ostrovem a významným centrem řecké kultury a umění.
Od roku 490 před naším letopočtem ovládli Naxos Peršané. Po řecko-perských válkách se stal ostrov součástí Athénského spolku. Za vlády Perikla se místní obyvatelé proti Athénám vzbouřili. To byl důvod, proč Athéňané vyvraždili mnoho místních lidí a ostrov kolonizovali athénskými občany.
Portara
V římské době zažíval Naxos prosperitu a klid. Postupně se tu začalo šířit křesťanství. Od roku 395 se stal Naxos součástí Byzantské říše. Zůstal bokem různých válečných konfliktů. Místní obyvatelé navazovali na svou kulturní minulost. Bylo postaveno mnoho kostelů a klášterů. Nádherné v nich zůstaly byzantské nástěnné malby.
V roce 1207 dobyla ostrov Benátská republika a několik Řeků přijalo katolickou víru.
Archeologické muzeum města Naxos
V 16. století obsadili ostrov Turci. Malá část zdejšího obyvatelstva přestoupila na islám. Místní Řekové několikrát povstali proti osmanské nadvládě a v roce 1821 se přidali k Řecké válce za nezávislost. Po vzniku Řecka mnoho obyvatel přesídlilo do Athén.
