We present results of phytolith analysis of deposits from three prehistoric settlement sites in Vanuatu: the small islands of Vao and Uripiv off the north east coast of the main island of Malekula and at Mafilau on the west coast of Epi Island. Samples from Vao Island coarsely encompass the period from Lapita times (c. 3000 BP) to the present. The data from this site suggest deforestation by people, with a decrease in palms and increase in grasses. The data from the three sites show evidence of an introduced cultigen during different prehistoric periods. Banana (Musa) phytoliths were found in one recent Vao layer (500 BP-present) and in Mafilau layers, the latter representing the immediate post-Lapita period (c. 2800-2500 BP). This phytolith type was also found at Uripiv in Lapita layers (c. 3000-2700 BP). Banana phytoliths are diagnostic so their presence in archaeological deposits in Remote Oceania, outside their natural distribution, provides secure evidence of cultivation. This demonstrates the potential of this line of evidence for identifying both the cultigens transported by early colonists and subsequent plant introductions. The data provide the first direct evidence of banana cultivation at a Lapita site in Remote Oceania and support the contention that horticulture was an integral part of the Lapita Cultural Complex.