В конце XVI века многие европейцы были уверены в существовании огромного континента в Южном полушарии, который должен был служить как бы противовесом земельным массивам Северного полушария. В поисках мифической «Южной земли» в 1567—1569 и 1595 годах испанцами были совершены два морских плавания на запад от Перу. Однако поиски были безуспешны: экспедициям под командованием Менданьи де Нейры удалось достичь только Соломоновых островов.
В 1598 году португалец Педро Фернандес де Кирос подал петицию испанскому королю Филиппу III о снаряжении новой экспедиции в Тихий океан. В 1600 году мореплаватель отправился в Рим, где впоследствии заручился поддержкой папы римского Климента VIII. В результате, в марте 1603 года Кирос был уполномочен отправиться в Перу с целью подготовки новой экспедиции, задачами которой стали поиски «Южной земли», расширение владений Испании и обращение местного населения в католичество.
Во время плавания, 25 апреля 1606 года, европейцами впервые был замечен один из островов в архипелаге Новые Гебриды — остров Мере-Лава в группе Банкс. 3 марта 1605 года был открыт остров Эспириту-Санто, названный Киросом «Austrialia del Esp?ritu Santo» (в переводе «Австрийская земля Святого духа»), таким образом, отдав должное королю Филиппу III, который являлся членом австрийской династии Габсбургов. Мореплаватель принял остров за часть таинственной «Южной земли», нового континента. Высадившись на нём, Кирос объявил открытую им землю территорией испанской короны и основал поселение Новый Иерусалим на реке Иордан.
Во время пребывания на острове путешественник сильно заболел, да и местное население относилось враждебно к чужеземцам. Спустя 35 дней судно Кироса отчалило с целью дальнейшего изучения «Южной земли». Однако вскоре погода сильно переменилась, изменилось направление ветра. Команде корабля не удалось вернуть корабль в бухту Эспириту-Санто, поэтому было решено взять курс к островам Санта-Крус в составе Соломоновых островов. Однако приблизившись к острову, команда решила направиться в Акапулько (Мексика). Путешественник ничего не смог поделать из-за своей болезни. Дальнейшие попытки Кироса снарядить новую экспедицию на Эспириту-Санто оказались безуспешными, и на протяжении 166 лет на Новых Гебридах не ступала нога европейца.
Праздничный обед людоедов на острове Танна, в представлении европейского художника
Французский исследователь Луи Антуан де Бугенвиль впоследствии доказал, проплыв вдоль южного берега Эспириту-Санто в 1768 году, что это был всего лишь остров. Острова, лежащие к северу от Эспириту-Санто, он назвал «Les Grandes Cyclades». В мае путешественник проплыл мимо островов Маэво и Пентекост, высадился на Оба. Пролив, разделяющий острова Эспириту-Санто и Малекула, был позже назван в честь французского мореплавателя.
В 1774 году во время своего второго кругосветного путешествия английский мореплаватель Джеймс Кук исследовал архипелаг и дал название островам «Новые Гебриды» в честь Гебридских островов, расположенных к западу от Шотландии. Путешественник сделал вывод, что острова Пентекост и Амбрим, открытые Бугенвилем, являются самостоятельными островами (ранее это не было известно), а на острове Амбрим есть два активных вулкана. По пути он проплыл мимо островов Паама и Лопеви, решив, что это один остров, открыл остров Эпи. В течение следующих нескольких недель Кук обследовал острова Эфате, Эроманга и Танна, попытался неудачно взобраться на вулкан Ясоур. Кук также собрал образцы древесины и пополнил запасы пресной воды, встретился с аборигенами, которые не впускали чужеземцев во внутренние районы островов. Исследовав остров Танна, корабль Джеймса Кука взял курс на север, к островам Малекула и Эспириту-Санто, а затем — на Новую Зеландию, так как путешественник посчитал, что исследовал все острова архипелага, хотя он так и не увидел островов Банкс и Торрес.
Впоследствии мимо Новых Гебрид проплывали и другие путешественники, однако многие из них не высаживались на островах.