К концу апреля они вошли в узкий пролив, по оценке секретаря Албукерка Корреа — «всего один пушечный выстрел в ширину». Этот момент считался историческим. Это был первый раз, когда христиане вошли в море в самом центре мусульманского мира. При этом совсем недалеко, на западном берегу, находилась земля, где, как считали португальцы, располагалось королевство пресвитера Иоанна на Эфиопском нагорье. «Мы вошли в пролив, — писал Албукерк, — и постарались сделать это как можно более внушительно, с пушечными залпами, трубами и флагами». Для губернатора это был особый момент. Португальцы оказались на пороге финального, самого важного завоевания. Проблема штурманов была легко решена — португальцы захватили проходившую мимо арабскую доу, затем двадцать человек спрятались под палубой, а когда в порту ни о чем не подозревающие штурманы поднялись на борт, они оказались в плену.
Они продвигались вперед, «не упуская из виду земли пресвитера Иоанна и побережье Аравии». По словам Корреа, их окружали весьма однообразные виды: «Штормов не было, только сильные порывы горячего ветра… по обе стороны земля иссушенная, никакой зелени, и горы». Из-за маленькой глубины плыть можно было только днем, пользуясь ватерпасом. На ночь же корабли вставали на якорь. Даже со всеми предосторожностями один из кораблей едва не сел на мель из-за ошибки штурмана.
Албукерк воспользовался тактикой запугивания, из-за которой франков так боялись на побережье Индии. Встречные корабли захватывали и грабили, забирая всю провизию. У несчастной команды отрезали руки, носы и уши, а затем высаживали их на берег, чтобы слухи о грозных и могучих португальцах распространились далеко. Затем захваченные корабли сжигали.
Первой целью Албукерка стал песчаный низкорасположенный остров Камаран, расположенный в 200 милях от входа в пролив возле Аравийского полуострова. Это был единственный источник пресной воды на всем протяжении побережья. Пополнив запасы воды, Албукерк решил отправиться в Джедду, однако ветер был весьма непостоянен. Направление его сменилось на западное, и, таким образом, дальнейшее продвижение вперед стало невозможным. Когда же ветер снова задул в восточном направлении, Албукерк поспешил пуститься в путь, однако тут ветер переменился снова. Двадцать два дня корабли простояли на якоре посреди моря, дожидаясь возможности плыть на север. Люди начали нервничать. Когда вода закончилась, оставалось только вернуться на Камаран. «И там они выжидали, — писал Корреа, — весь май, июнь и июль, без дождей». Португальцы оказались в ловушке. На острове водились козы и верблюды, которыми они питались. Кроме того, португальцы ловили рыбу. Их окружали мангровые болота и низкие кустарники, росшие на песке под жарким солнцем. Несмотря на все тяготы, Албукерк продолжал сохранять бодрость и оптимизм. Он отправлял маленькие каравеллы в разведывательные экспедиции, приказывал захватывать проходящие мимо корабли и допрашивал их команды, таким образом узнавая нужные сведения об этой земле. Кроме того, к недовольству своих людей, Албукерк приказал, чтобы каменщики попытались изготовить известь. Они сообщили, что это возможно. «Мы нашли много подходящей горной породы, а также камни домов, мечетей и старинных зданий… это лучшее и самое удобное место для форта в мире, — писал Албукерк королю. — Гавань, защищенная от всех ветров… воды в изобилии… много хорошей рыбы». Люди боялись, что Албукерк потребует возведения еще одного форта.
Для короля и придворных в Лиссабоне Албукерк расписывал остров как прекрасное место. Однако же эти рассказы не соответствовали действительности. Когда Албукерк приказал готовиться к отплытию с Камарана в Джедду, португальцы принялись возражать, утверждая, что «он их погубит». Вопреки оптимистичным письмам королю, много людей умерло. Продовольствия на острове было мало, к тому же португальцам приходилось тяжело трудиться, чиня корабли. Люди начали умирать от загадочной эпидемии: «После всего двух или трех приступов лихорадки и сильной боли в груди от неизвестной болезни, от которой кровь заполняет грудь, умерло много народу, больше пятисот [из тысячи семисот] и почти все местные — от тяжелой работы и скудного питания». Об этом Албукерк не написал королю ни слова.
Губернатор верил, что эта миссия — богоугодное дело, что было подтверждено чудесным знаком в ночном небе. Однажды безлунной ночью, «…когда мы стояли на якоре в этом месте, над землями пресвитера Иоанна нам явился знак в небесах в форме ярко сияющего креста, над которым висело облако. Когда облако достигло креста, оно распалось на части, не успев коснуться его или затуманить его яркость. Это было видно с кораблей, и многие в восхищении упали на колени. У некоторых на глазах от восторга выступили слезы».
Албукерк пытался уговорить штурманов и капитанов пересечь море против ветра и подойти к западному берегу, однако те отказались. В течение этих месяцев, проведенных под жарким солнцем среди песчаных дюн, Албукерк продолжал составлять подробный отчет о Красном море, который позже отослал в Лиссабон. Он узнал все, что мог, о климате, географии и навигации в этих местах, а также о городах-портах, политике и отношениях между племенами. Он отправил каравеллы исследовать жемчужные поля, а также интересовался месторождениями золота в землях пресвитера Иоанна. Наконец, к облегчению португальцев, Албукерк пришел к заключению, что находившаяся на западном берегу Массава будет лучшим местом для крепости, чем остров, на котором они сейчас находятся. Албукерк объяснил решение тем, что «на ближних берегах правит пресвитер Иоанн». Вера в могущество этого полумифического христианского правителя была по-прежнему сильна. «Теперь я располагаю полными сведениями обо всем, что касается Красного моря», — сообщил Албукерк Мануэлу.
Португальская разведка работала крайне активно. Всегда находились смельчаки, готовые к самым рискованным приключениям. По примеру Перу да Ковильи, шпиона, которого король Жуан направил в Индию, человек по имени Фернан Диаш вызвался совершать разведывательные экспедиции на дальние
