In the not too distant past, most archaeologists believed that most of the world’s islands were not inhabited until relatively recent times, after the introduction of food producing Neolithic economies.  In recent years, however, convincing evidence has emerged for far earlier Paleolithic occupations, such as on of Flores in Indonesia, home of the controversial “hobbit” hominins. Now, some Mediterranean islands, such as Crete and Naxos, also suggest possible pre-Homo sapiens use.  While this remains rare, there is compelling evidence for use of some islands immediately before the Neolithic, with some of the best evidence coming from Cyprus.  The narrative of a late Neolithic-only occupation was dramatically challenged by the controversial site of Akrotiri Aetokremnos, dating to about 12,000 years ago.  Aetokremnos also suggests that humans were instrumental in the extinction of native animals, including the pygmy hippopotamus.  Newer investigations also have expanded the Neolithic of Cyprus, which now is as old as that of the mainland. This presentation summarizes these new investigations that have re-written the story of how and when the Mediterranean islands were first visited and subsequently colonized.