Mljetin löysivät muinaiset kreikkalais-roomalaiset maantieteilijät, jotka kirjoittivat ensimmäiset tiedot ja kuvaukset. Saaren kuvasi ensimmäisen kerran Scylax of Caryanda 6. vuosisadalla eaa.; toiset suosivat tekstiä Periplus of Pseudo-Scylax. Molemmissa teksteissä se on nimeltään Melite ja sitä tukee Apollonius Rodoslainen. Agathemerus ja Plinius vanhempi kutsuvat saarta nimellä Melita.
Rooman keisari Septimius Severus (145-211 jKr.) karkotti Kilikiassa sijaitsevan Anaxarban Agesiluksen, Oppianuksen isän, Mljetille (tai Lucius Verus Maltalle: ks. Oppianus).
Bysantin keisari Konstantinus VII Porphyrogenitos mainitsee Mljetin vuoden 950 tienoilla teoksessaan Of Ruling an Empire (Valtakunnan hallitsemisesta) yhtenä narentiinien hallussa olleista saarista. Saaresta käytiin usein omistuskiistaa heidän ja Zachlumian välillä. Muinaiset kreikkalaiset kutsuivat saarta nimellä ”Melita” eli ”hunaja”, joka vuosisatojen kuluessa kehittyi slaavilaiseksi nimeksi Mljet (lausutaan ).
Mljetiä on pidetty ”Melitana”, jolle pyhä Paavali haaksirikkoutui (Apostolien teot 27:39-28:11), ja tätä näkemystä esitti ensimmäisen kerran 10. vuosisadalla itäisen Rooman keisari Konstantinus Porphyrogenitus. Pyhän Paavalin haaksirikko sijoitetaan yleensä Välimeren Maltan saarelle. Mljetillä ja Maltalla oli kreikkalaisissa ja roomalaisissa lähteissä sama nimi; Apostolien teot 28:3-5:ssä olevan kyykäärmeen maininnan uskottiin puoltavan Mljetin nimeä (sekä Mljetillä että Maltalla on käärmeitä, mutta vain ensiksi mainitulla on myrkkykäärme). Molemmilla saarilla on pyhimyksen mukaan nimetty satama.
Apulian Pulsanosta kotoisin olevista benediktiiniläisistä tuli saaren feodaaliherroja vuonna 1151, kun he olivat tulleet Monte Garganosta Italiasta. He rantautuivat Sutmiholjskan poukamaan, ja vuosina 1187-1198 Vojislavljevićin talon serbialainen ruhtinas Desa rakensi ja lahjoitti heille Pyhän Marian kirkon ja luostarin Ison järven (Veliko Jezero) saarekkeelle saaren luoteispäässä. Paavi Innocentius III antoi vuonna 1198 asiakirjan, jossa kirkko vihittiin käyttöön.
Benediktinuslaiset luopuivat Mljetin hallinnasta vuonna 1345 ja pitivät hallussaan vain kolmanneksen maasta. Saari sai statuutin ja kunnan Babino Poljessa. Se liitettiin virallisesti Ragusan tasavaltaan vuonna 1410. Benediktinuslaisten kanssa tehdyn sopimuksen mukaan kunnan oli maksettava vuosittain 300 perpparia.
1500-luvulla luostari oli Mljetin kongregaation (Congregatio Melitensis tai Melitana) keskus, joka kokosi yhteen kaikki Ragusan tasavallan alueella toimivat benediktiinimunkkien luostarit. Kongregaation ensimmäinen puheenjohtaja oli Mavro Vetranović, Mljetin luostarin apotti ja kuuluisa runoilija. Toinen suuri runoilija oli luostarin apotti Ignjat Đurđević 1700-luvulla. Ajan myötä Mljetin benediktiiniluostari menetti merkitystään, ja Mljetin kongregaation kotipaikka siirtyi Sveti Jakoviin Ragusan lähelle.
Vuonna 1809, Napoleonin vallan aikana, Mljetin luostari lakkautettiin. Kun Itävalta otti saaren haltuunsa, se sijoitti rakennukseen metsätoimiston. Maailmansotien välillä rakennus oli Ragusan (Dubrovnikin) piispakunnan omistuksessa. Vuonna 1960 siitä tuli hotelli, ja vuonna 1998 se palautettiin piispakunnalle. Saarella on pitkä historia ympäristötuhoista. Helpottaakseen kuljetusongelmiaan munkit kaivoivat kanavan etelärannikolle Veliko Jezero -järvestä, jolloin molemmat makean veden järvet muuttuivat merivesipohjaisiksi.
Toinen välikohtaus liittyy mungoihin. Pienet aasialaiset mungot istutettiin saarelle 1900-luvun alussa myrkkykäärmekannan vähentämiseksi (saari oli ilmeisesti täysin vallattu). Vaikka mungot suorittivat tämän tehtävän, ne myös hävittivät lähes koko saaren linnuston. Vielä tänäkin päivänä saarella on huomattavan vähän pensasaitojen lintuja, kuten varpuslintuja. Mungot ovat vaaraksi kotieläiminä pidetylle siipikarjalle, ja niiden tiedetään myös aiheuttavan vahinkoa viinitarhoissa ja hedelmätarhoissa.