The island of Cyprus has a long history of human impacts, including the introduction of more than 250 plant species. One of these introduced species is Juglans regia (walnut), which is considered a naturalised non-native (introduced in last 500 years). Here we report the earliest occurrence of Juglans regia pollen grains from a sedimentary deposit on Cyprus. The pollen recovered from the Akrotiri Marsh provides an earliest introduction date of 3,100-3,000 cal yr bp. This Bronze Age occurrence of Juglans regia is sporadic. However, by 2,000 cal yr bp the pollen signal becomes more persistent and indicates that introduction or expansion of Juglans regia was highly likely in the Roman period. We integrate our new results with younger pollen occurrences of Juglans regia on Cyprus, the archaeobotanical record and documentary evidence to provide an overview of this archaeophyte. Our findings show that, following the conventions of the Flora of Cyprus, Juglans regia should be reclassified from naturalised non-native to indigenous.