Как бы то ни было, испанцы нашли чернокожих людей, описанных им инками. С первой попытки в 1568 году они дошли из Перу до Меланезии. Раздоры на корабле вынудили их отклониться от пути, который, по словам инкских историков, вел к ближайшему обитаемому острову (позднее выяснилось, что путь этот ведет к острову Пасхи). Изменив курс, испанцы прошли южнее Маркизов и не встретили суши до самых Соломоновых островов; здесь они первыми из европейцев увидели чернокожих меланезийцев. С великим трудом удалось им возвратиться в Южную Америку, и в 1595 году они снова отплыли из Перу. Идя на этот раз прямо на запад, мореплаватели увидели горы Фату-Хивы. Обогнули остров, остановились с подветренной стороны, и состоялась первая встреча европейцев с полинезийцами. Хотя на берегу острова стояли люди, испанцы приписали себе честь его открытия.

Из записей штурмана Педро Фернандеса де Кироса следует, что четыре каравеллы испанцев бросили якорь в заливе Омоа . Обнаруженный ими остров был «густо населен». Четыре сотни островитян на лодках и вплавь добрались до кораблей, чтобы приветствовать гостей, и толпы людей сгрудились на пляже и скалах. Сорок человек поднялись на борт, «и испанцы казались малорослыми рядом с ними». Один островитянин на голову возвышался над всеми остальными. Несколько человек отличались светлой кожей и «рыжеватыми волосами». О других сказано, что они были «не просто светлокожие, а белые». Один старый вождь с зонтом из пальмовых листьев щеголял холеной бородой, на которую свисали такие длинные усы, что он раздвигал их двумя руками, когда выкрикивал распоряжения. На другой день адмирал Менданья самолично сошел на берег вместе с супругой, чтобы присутствовать при первом католическом богослужении в Полинезии. Штурман отмечает: «Рядом с доньей Исабелой сидела чрезвычайно красивая туземка с такими рыжими волосами, что донья Исабела захотела отрезать несколько прядей, однако видя, что туземка против, воздержалась, чтобы не сердить ее».

В то время как супруга адмирала любезно воздержалась от покушения на рыжие волосы, солдаты адмирала забавы ради навели свои аркебузы на старого бородача с зонтом и убили его, а заодно еще семь-восемь островитян.

Совершив таким образом открытие Фату-Хивы, который они назвали Магдаленой, испанцы пошли на север и увидели Мотане, в то время «остров прекрасного вида с густыми лесами и тучными нивами». Однако они проследовали мимо, привлеченные контурами более крупных Тахуаты и Хива-Оа, и объявили все четыре острова владениями Его Величества Короля. Научили одного туземца говорить «Иисус Мария» и осенять себя крестным знамением, после чего застрелили две сотни других туземцев. Одного испанского солдата спросили, почему он, сидя в гостях в туземной хижине, стреляет по проходящим мимо островитянам; он ответил, что ему нравится убивать. Штурман рассказывает, что другой солдат иначе оправдал свой поступок, когда убил туземца, который, пытаясь спасти свою жизнь, прыгнул в море с ребенком на руках. Туземцу, говорил этот солдат, все равно место в аду, а слава меткого стрелка не позволяет ему промахиваться.»

Адмирал повелел корабельному священнику и его викарию петь «Те Деум лаудамус» перед коленопреклоненными туземцами; были установлены три креста; острова получили благословение и христианские наименования. После чего испанцы подняли якоря и продолжили путь на запад, поскольку на Маркизах не нашлось золота.

До отплытия испанцы переспали с местными женщинами и в знак благодарности посеяли кукурузу в присутствии туземцев. Однако условия для венерических болезней явно оказались более благоприятными, чем для кукурузы: сифилис распространился со скоростью степного пожара, а кукуруза так и не проросла.