Historie ostrova Milos je úzce spjata s jeho sopečným původem a bohatstvím nerostných surovin, které z něj učinily jedno z nejdůležitějších obchodních center starověku. Milos byl osídlován již v době neolitu. Díky těžbě obsidiánu (tvrdé sopečné sklo využívané k výrobě nástrojů a zbraní) byl ostrov klíčovým obchodním centrem. V období cca 2 300 - 1 100 př.n.l. vzniklo město Phylakopi, jedno z center kykladské civilizace. Město bylo opakovaně zničeno a znovu postaveno. Po úpadku Phylakopi (cca 1000 př. n. l.) ostrov ovládali Dórové ze Sparty. Ti také založili nové město v oblasti dnešní osady Klima. V roce 416 př. n. l. v době Peloponéské války dobývají ostrov Athény. Dochází k likvidaci mužů, ženy a děti padnou do otroctví (popis ve slavném Mélijském dialogu, který je dodnes studován jako příklad mocenského pragmatismu). Po porážce Athén přichází vláda Ptolemaiovců a později Římanů. Ostrov začne opět prosperovat. Z této doby pochází známé mramorové divadlo a vznikají křesťanské katakomby. V roce 1207 se Milos stal součástí benátského Vévodství Naxos. Od roku 1566 jej ovládali Osmané. Od roku 1830 je Milos součástí řeckého státu.
Během 2. světové války sehrává Milos klíčovou strategickou roli. Německá vojska obsadila Milos 6. května 1941, krátce po dobytí pevninského Řecka. Na ostrově bylo postupně rozmístěno přes 4 000 německých vojáků. Němci zde vybudovali systémy protivzdušné obrany, dělostřelecké baterie (např. v oblasti Trahilas) a radarové stanice (např. na hoře Topakas). Přístav sloužil jako důležitý uzel pro přesuny vojsk mezi Attikou a Krétou.
V roce 1943 vybudoval wehrmacht v hlavním městě Plaka podzemní bunkr, který sloužil jako vojenská nemocnice a sklad munice. Dnes se v něm nachází Válečné muzeum (War Museum). Dne 23. února 1943 popravili Němci 14 místních civilistů. Byli obviněni z rabování nákladu z potopené německé lodi SS Artemis Pitta. Ke konci války (listopad 1944) podnikaly britské a řecké speciální jednotky nájezdy na německé radarové stanice a dělostřelecké pozice, aby oslabily německou posádku, která na ostrově zůstala odříznutá. Milos byl nakonec jedním z posledních míst v Řecku, které bylo osvobozeno. Německá posádka (čítající přes 500 mužů) se oficiálně vzdala až 8. května 1945 a řecká vlajka byla nad ostrovem vztyčena 9. května toho roku.