Predictive models have become an integral part of archaeological research, particularly in the discovery of new archaeological sites. In this paper, we apply predictive modeling to map high potential Pleistocene archaeological locales on the island of Cyprus in the Eastern Mediterranean. The model delineates landscape characteristics that denote areas with high potential to unearth Pleistocene archaeology while at the same time highlighting localities that should be excluded. The predictive model was employed in surface surveys to systematically access high probability locales on Cyprus. A number of newly identified localities suggests that the true density of mobile hunter-gatherer sites on Cyprus is seriously underestimated in current narratives. By adding new data to this modest corpus of early insular sites, we are able to contribute to debates regarding island colonisation and the role of coastal environments in human dispersals to new territories.