Milos è abitata fin dal Neolitico grazie alla sua ossidiana — il vetro vulcanico nero che, tagliente come una lama, divenne un prezioso oggetto di commercio in tutto l'Egeo e il Mediterraneo molto prima dell'età dei metalli. L'insediamento preistorico di Fylakopi emerse come importante centro della Civiltà Cicladica, con stretti contatti con la Creta minoica e la Grecia micenea.
Nell'antichità classica Milos era indipendente e prospera, colonia dei Dori spartani. Nel 416 a.C., durante la Guerra del Peloponneso, gli Ateniesi assediarono e conquistarono violentemente l'isola in un episodio che Tucidide immortalò come il «Dialogo dei Meli» — un testo senza tempo sulla legge del più forte.
Nei primi secoli cristiani Milos divenne rifugio dei primi cristiani, che scavarono le impressionanti Catacombe. In epoca bizantina e veneziana l'isola, con il suo porto sicuro, conobbe incursioni piratesche ma anche attività commerciale, mentre Plaka con il Castello divenne il centro fortificato.
Nel 1820, un contadino trovò in un campo di Trypiti la Venere di Milo, una delle sculture più famose al mondo, finita al Louvre. La storia più recente è stata segnata dall'attività mineraria — zolfo, caolino, bentonite, perlite — che rimane viva ancora oggi, mentre negli ultimi decenni Milos è diventata una destinazione turistica di primo piano grazie alle sue spiagge uniche e colorate.