The archipelago of Vanuatu has been at the crossroads of human population movements in the Pacific for the past three millennia. To help address several open questions regarding the history of these movements, we generated genome-wide data for 11 ancient individuals from the island of Efate dating from its earliest settlement to the recent past, including five associated with the Chief Roi Mata's Domain World Heritage Area, and analyzed them in conjunction with 34 published ancient individuals from Vanuatu and elsewhere in Oceania, as well as present-day populations. Our results outline three distinct periods of population transformations. First, the four earliest individuals, from the Lapita-period site of Teouma, are concordant with eight previously described Lapita-associated individuals from Vanuatu and Tonga in having almost all of their ancestry from a "First Remote Oceanian" source related to East and Southeast Asians. Second, both the Papuan ancestry predominating in Vanuatu for the past 2,500 years and the smaller component of Papuan ancestry found in Polynesians can be modeled as deriving from a single source most likely originating in New Britain, suggesting that the movement of people carrying this ancestry to Remote Oceania closely followed that of the First Remote Oceanians in time and space. Third, the Chief Roi Mata's Domain individuals descend from a mixture of Vanuatu- and Polynesian-derived ancestry and are related to Polynesian-influenced communities today in central, but not southern, Vanuatu, demonstrating Polynesian genetic input in multiple groups with independent histories.