Албукерку оставалось только подбирать обломки. Отступая, португальцы подобрали фрагменты сломанных лестниц, чтобы «не оставлять их в качестве свидетельства хаоса, царившего в наших войсках». Если верить хроникерам, губернатор был «так потрясен тем, что Аден был для нас потерян при подобных обстоятельствах, в таком беспорядке, что даже не смог ничего сказать по этому поводу».

Настроение в португальском лагере было весьма раздосадованным. В субботу на Пасхальной неделе, положившись на Божью помощь, они потерпели неудачу. Португальцы рвались предпринять еще одну попытку, собираясь пробить дыру в стене при помощи самых мощных пушек. Однако Албукерк понимал, что они упустили подходящий момент. Самой важной проблемой был недостаток воды. Кроме того, нельзя было забывать и про сезон дождей. Если не уйти сейчас, можно было оказаться в отчаянной ситуации. Португальцы не могли бы ни выйти в Красное море, ни вернуться через Индийский океан.

Захватить Аден оказалось не так легко. Албукерк еще не отдавал себе отчета, какую трудную задачу взвалил на свои плечи. Отчитываясь о результатах экспедиции перед королем, он попытался выставить ситуацию в выгодном свете — насколько это было возможно: «Относительно происходившего в Адене могу заверить Ваше Величество, что это была самая свирепая и быстрая атака из всех, какие только можно вообразить… желание людей послужить вам удвоило их силы, и лестницы сломались под весом толпы людей, стремившихся как можно лучше послужить вам в тот день».

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

До предпринятой Албукерком операции португальские карты Красного моря практически пустые, хотя Камаран обозначен (под названием Каморам)

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

Они продвигались вперед, «не упуская из виду земли пресвитера Иоанна и побережье Аравии». По словам Корреа, их окружали весьма однообразные виды: «Штормов не было, только сильные порывы горячего ветра… по обе стороны земля иссушенная, никакой зелени, и горы». Из-за маленькой глубины плыть можно было только днем, пользуясь ватерпасом. На ночь же корабли вставали на якорь. Даже со всеми предосторожностями один из кораблей едва не сел на мель из-за ошибки штурмана.

Албукерк воспользовался тактикой запугивания, из-за которой франков так боялись на побережье Индии. Встречные корабли захватывали и грабили, забирая всю провизию. У несчастной команды отрезали руки, носы и уши, а затем высаживали их на берег, чтобы слухи о грозных и могучих португальцах распространились далеко. Затем захваченные корабли сжигали.

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

Для короля и придворных в Лиссабоне Албукерк расписывал остров как прекрасное место. Однако же эти рассказы не соответствовали действительности. Когда Албукерк приказал готовиться к отплытию с Камарана в Джедду, португальцы принялись возражать, утверждая, что «он их погубит». Вопреки оптимистичным письмам королю, много людей умерло. Продовольствия на острове было мало, к тому же португальцам приходилось тяжело трудиться, чиня корабли. Люди начали умирать от загадочной эпидемии: «После всего двух или трех приступов лихорадки и сильной боли в груди от неизвестной болезни, от которой кровь заполняет грудь, умерло много народу, больше пятисот [из тысячи семисот] и почти все местные — от тяжелой работы и скудного питания». Об этом Албукерк не написал королю ни слова.