Sota l'imperi bizantí fou atacada per pirates eslaus i àrabs. La capital fou destruïda per un terratrèmol i fou traslladada a l'àrea de Komia i Embórios.
Revoltes religioses als seglesegles VIII i IX foren reprimides pels bizantins. El 1207 va passar als Sanudo de [[ducat de Naxos|Naxos]] i els ducs de Naxos la van conservar formant una senyoria del [[1341]] al [[1383]]. La dinastia Sanudo va donar passar als [[Crispo]] el [[1383]] quan [[Francesc I Crispo]] va agafar el poder en una revolta armada i es va casar amb l'hereva Fiorenza Sanudo. Els Crispo, ducs de Naxos i senyors de Melos, la van mantenir fins que fou entregada als otomans el [[1566]]. El jueu [[Josep Nasi]] va governar les illes del [[1566]] al [[1579]], i després va passar a domini directe otomà amb un acord de govern autònom local: l'illa pagava taxes però mai no fou ocupada per una guarnició.
El [[1661]] els venecians van derrotar els turcs en una batalla naval en aigües de l'illa.
