Prvi stanovnici na Mljetu bili su Iliri iz plemena Ardijejaca koji su preko luke Prapratno na poluotoku Pelješcu došli na Mljet prije 4000 godina. Prvi doticaj s Mljetom imali su u lukama Sobra i Okuklje, koje su bile najbliže Pelješcu, ali su također došli u doticaj s lukama Polače i Kozarica. Došavši na potpuno pošumljeni otok, polako su se naseljavali uz izvore pitke vode i uz rubove otočkih dolova. Živjeli su u malenim nastambama sagrađenim od suhozida, dok su ih pokrivali granama makije i bora. Bavili su se stočarstvom, poglavito uzgojem koza i ovaca, lovom i ribolovom.
Prvi povijesni zapisi o otoku Mljetu vezani su za grčke moreplovce koji su ploveći prema svojim kolonijama na Korčuli, Visu i Hvaru sigurno prolazili kroz Mljetski kanal te se sklanjali u mljetske uvale za vrijeme jakih južnih vjetrova. Osim za vrijeme nepovoljnog vremena, Grci su se sklanjali u zaljeve Sobra i Polače zbog izvora pitke vode koji su bili u blizini morske obale. Materijalnih dokaza o stanovanju Grka na Mljetu nema pa se dâ zaključiti kako Grci otok nisu ni naseljavali, već su ga koristili za odmor i kao zaklon od lošeg vremena. Dokaz tome su podmorska nalazišta grčkih amfora u današnjim lukama Okuklje, Sobra i Polače, koja su nastala usred stradavanja brodova u nevremenu ili za vrijeme gusarskih napada.
Mljet je pod vlast Rimljana došao 167. godine pr. n. e. kad je ardijejski vladar Gencije zaratio protiv Rima i u tom ratu bio pobjeđen. U to su vrijeme Rimljani osvojili područje do današnje Albanije. Vlast Rima na Mljetu je bila nominalna jer su Iliri i dalje gusarili Mljetskim kanalom. Prve konkretne podatke o Mljetu nalazimo kod rimskog pisca Apijana, koji je opisivao ratove cara Augusta s lokalnim stanovništvom na Mljetu. Apijan u svojem djelu De rebus Illyricis navodi kako je August razorio ilirski grad Melitusu 35. godine pr. n. e. zbog učestalih gusarskih napada na rimsko brodovlje. Pokoravanjem lokalnog stanovništva, Rimljani u zaljevu Polače tijekom 3. stoljeća počinju graditi impozantnu palaču u kojoj je stolovao rimski upravitelj ovog posjeda. Palača je imala i obrambenu funkciju o čemu svjedoče dvije jake kule na njezinim krajevima. Uz palaču su tokom vremena izgrađene i dvije ranokršćanske bazilike i terme, što ukazuje da je u palači, osim upravitelja živjelo i svećenstvo, a to nam govori da je Polače u ono vrijeme živjelo i funkcioniralo kao kasnoantički, odnosno ranosrednjovjekovni grad.
Neretljani su na Mljet došlipreko Pelješca, isto kao i Iliri, a svoje su naselje (prvo slavensko naselje na Mljetu) izgradili iznad današnjeg naselja Maranovići i nazvali su ga Vrhmljeće.
U 12. stoljeću benediktinci sa sjedištem u samostanu na Otočiću sv. Marije postaju gospodari cijelog Mljeta te su u vrlo kratkom roku utvrdili svoju feudalnu vlast na cijelom otoku. Benediktinci su svu hranu proizvodili sami svojim radom, a domaćem su stanovništvu pokazivali kako uzgajati pojedinu kulturu što je uvelike unaprijedilo poljoprivredu na otoku. Osim za gospodarstvo, benediktinci su odigrali veliku ulogu u razvoju pismenosti. Smatra se da je knjižnica samostana na Mljetu pripadala među deset najvećih benediktinskih opatija u cijeloj Dalmaciji. S vremenom su benediktinci postali i crkvena i civilna vlast na otoku. Posebnom listinom, "Mljetskim statutum", izdanom u Dubrovniku 24. rujna 1345. godine, samostan oslobađa sve otočane od svih kontribucija i službi prema opatiji.
Nakon donošenja Mljetskog statuta 1345. godine i nakon oslobađanja otočana od kmetske podložnosti, Dubrovčani su se polako počeli pripremati da što prije uspostave svoju vlast na Mljetu. 15. studenog 1410. godine Veliko vijeće donosi propise o Mljetu čime je Mljet definitivno postao dio Dubrovačke Republike. Mljet će pod Dubrovnikom ostati sve do ukidanja Republike 1808. godine.