Четырнадцать членов португальского посольства были не самыми лучшими представителями своей страны. Всем управлял Родриго да Лима. Его назначили лишь недавно, так как посол короля Мануэла, семидесятидвухлетний дипломат, умер за месяц до этого и был похоронен в песке одного из прибрежных островов. Да Лима был молод, раздражителен и бестактен и уже начал ссориться со своим заместителем, Жоржи д’Абреу, считавшим себя более достойным возглавить посольство. Сохранять спокойствие между двумя забияками пытался отец Франсишку Альвареш, ранее бывший капелланом короля Мануэла, а теперь священник, на котором лежала ответственность за изучение и описание религии пресвитера Иоанна. Его дневник стал первым свидетельством об Эфиопии, изданным в Европе. В посольство также входили менее важные персоны: писарь, художник, который должен был переносить на холст интересные картины, открывавшиеся взору путешественников, а также делать наброски для развлечения пресвитера Иоанна в его дворце, музыкант, привезший с собой переносной орган (опять-таки для развлечения пресвитера Иоанна), брадобрей (по совместительству врач) и несколько португальских слуг, в основном взятых за способность мелодично петь во время церковной службы. В качестве даров они изначально намеревались привезти огромную кровать. Ее балдахин, отделанный синими и желтыми занавесями из тафты, изображал императора, коронующего королеву, и четыре трубача. Одеяла, на которых был вышит португальский герб, дополняли подарок. К сожалению, кровать не перенесла морского путешествия, и, обследовав скудные запасы, оставшиеся на корабле, да Лима обнаружил, что располагает четырьмя гобеленами, органом, золотым мечом с богатой рукояткой, двумя вышедшими из употребления ружьями с сохранившимся зарядом, несколькими деталями боевого облачения и картой мира. Это было весьма скудное подношение для такого могущественного правителя, как пресвитер Иоанн.
От Массауа на берегу Красного моря, где высадилось посольство, было около 720 километров по прямой до Шоа, где обычно располагался двор негуса. Все сложности пути можно представить, если принять во внимание, что на преодоление этого расстояния португальцам потребовалось полгода. С палуб своей эскадры они видели пугающие очертания голых скал, высившихся сразу за выгоревшей белизной побережья. Похожие на крепости монастыри, выстроенные на высоких вершинах, и чудесное явление креста, сверкающего в ночном небе над холмами, заставило нескольких матросов дезертировать и сойти на берег в поисках славы и мирских выгод. Но большинство из них вскоре вернулись обратно, отступив перед дикостью этой земли. Не было дорог, ведущих в глубь страны, существовало лишь несколько узких троп, что вились от одной деревушки или монастыря к другим. От моря к плато Шоа вел головокружительный подъем – изматывающий путь посреди спекшегося известняка, русел высохших ручейков и бесплодной почвы, усеянной горной породой. Это давило на людей так же, как в худших областях Португалии, – только названия были другими. Знакомые «месы» – на Пиренейском полуострове так называли плоскогорья – в Эфиопии именовались «амбами», и если – как позже обнаружило посольство – пресвитер Иоанн использовал самые недосягаемые вершины в качестве тюрем для своих соперников, то это ненамного отличалось от португальской привычки заточать врагов правящей династии в подземелья Альджубарроты.
