The leafless Vanilla species complex from the South-West Indian Ocean (SWIO) region has long been a taxonomic challenge, due to limited patterns of morphological differentiation and an absence of variation within chloroplast sequences. This complex includes seven known morphospecies: V. madagascariensis, V. bosseri, V. decaryana, and V. perrieri endemic to Madagascar, V. humblotii presumed as endemic to the Comoros Archipelago, but also present in Madagascar, V. roscheri from the East African coast, and V. phalaenopsis endemic to Seychelles. A previous population genetic study using microsatellite markers allowed us to distinguish, in addition to the five recognized Malagasy taxa, two other genetic clusters present in the East of the island. An integrative taxonomy approach was therefore conducted by combining microsatellite and morphological data used in the previous study with new data sets, and by adding ITS sequencing data, to validate the taxonomic level of these Malagasy genetic clusters and unravel phylogenetic relationships between SWIO species. As a result, based on phylogenetic, genotypic and morphological evidence, nine species were discriminated in the SWIO region, including seven in Madagascar, with two new eastern species. The leafless Vanilla group originated and diversified in Madagascar, from an ancestor of African descent, with three subsequent independent colonization events from Madagascar to the other territories of SWIO within the two main lineages (white versus yellow flower species). The new Malagasy species, V. allorgeae Andriamihaja & Pailler sp. nov., and V. atsinananensis Andriamihaja & Pailler sp. nov., are described and a new identification key is proposed.