Жуан поручил строительство форта в Эльмине Диогу де Азамбухе, придворному дворянину и надежному военному , который уже успел зарекомендовать себя в различных кампаниях, в том числе против Марокко и Кастилии. Одним из его товарищей по экипажу был Бартоломеу Диаш, дворянин, который семь лет спустя станет первым европейцем, достигшим южной оконечности Африки и вышедшим оттуда в Индийский океан. В течение следующих нескольких лет ряд других гигантов эпохи открытий также будут привлечены к снабжению или управлению первым крупным форпостом Португалии к югу от Сахары, что подтверждает роль Эльмины как стержня в зарождающемся глобальном проекте Лиссабона. Среди них были Афонсу де Альбукерке, который позже проложил тропу имперских завоеваний в Азии, и Диогу Кау, который "открыл" Конго, крупное королевство далеко на юго-востоке. Пока достаточно сказать, что в Лиссабоне миссия Кау в Конго была приоритетнее поисков пути в Индию, и в течение многих лет после этого он был более известной фигурой в Португалии, чем Диаш. Кау был возведен из эсквайра в рыцари королевского двора, ему было пожаловано щедрое жалованье и герб. Диаш, напротив, получилне никаких особых почестей за то, что доказал возможность плавания из Португалии в Индийский океан, и нет никаких сведений о королевской аудиенции для него по возвращении. А вот сам Христофор Колумб, который в то время также находился на службе у Лиссабона. В своей переписке он обнадеживающе свидетельствует о том, что опасения европейцев по поводу негостеприимных условий жизни в этой части Африки, расположенной всего в нескольких градусах к северу от экватора, были сильно преувеличены. " Я был в замке Ла-Мина короля Португалии... и я хороший свидетель, что он не необитаем, как говорят", - писал Колумб о визите, состоявшемся в 1482 году, в первый же год существования достроенного форта.
В декабре 1481 года, когда конвой отплыл к побережью Мины, внимание к деталям, проявленное при планировании персонала и поставок, говорило о важности миссии для Португалии; Эльмина прошла очень долгий путь с тех пор, как между короной и Гомешем был заключен первый королевский контракт на торговлю здесь за сущие гроши. Всего было десять каравелл, на которых находилось пятьсот военных, а также еще сто каменщиков и других специалистов по различным строительным специальностям. Два более тяжелых и медленных транспортных корабля были отправлены за несколько недель до этого с указанием ожидать основной контингент в заранее назначенной точке далеко от африканского побережья. Эти грузовые суда везли не только известь, кирпич, гвозди и древесину, но и основные части фундамента и краеугольные камни для форта, которые были заранее заготовлены и тщательно промаркированы. Ничто не было оставлено без внимания, включая оборону сооружения, для которой на борту также были установлены пушки и многочисленные боеприпасы .
Экспедиция Диогу де Азамбужа достигла вод современной Ганы в середине января. До сих пор большая часть португальской торговли золотом была сосредоточена вокруг Шамы, но эта деревня была признана неподходящим портом для больших кораблей, к тому же в ней не было доступных запасов пресной воды и крупных камней, необходимых для кладки настоящего форта. Поздно вечером 19 января, проплыв еще двадцать пять миль на восток, конвой достиг Деревни Двух Частей - поселения, которое было рассечено надвое узкой рекой с медленным течением. С вершины холма, с которого открывается вид на Эльмину, привлекательность этого места вряд ли может быть более очевидной. При подходе с запада неровная, усыпанная валунами береговая линия переходит в дугу широкой бухты, которая так хорошо укрыта, что на ее извилистый песчаный пляж накатывают лишь самые слабые волны. Здесь, на безопасном расстоянии от берега, португальский конвой мог бы спокойно стоять на якоре, не опасаясь ни нападения местных жителей, ни посадки на мель. Более того, устье реки, которая, как они узнали, называется Беня, было судоходным на небольшом расстоянии от ее устья, что давало возможность сразу же попасть в оживленную рыбацкую деревушку и на красочный рынок, которые и сегодня заполонили берега реки.
Когда в тот день в начале 1482 года Азамбужа привел свой корабль в устье Беньи, он и его люди, вероятно, были удивлены, обнаружив, что парусник, принадлежащий несанкционированному португальскому торговцу , уже стоит на якоре, так сказать, перед флагом. Благодаря длительному пребыванию или неоднократным визитам капитан этого судна, Жуан Фернандо, уже провел достаточно времени в этом районе, чтобы достаточно хорошо общаться на местном языке фанте. Поэтому Азамбужа, , попросил своего соотечественника на рассвете следующего утра отправить местному королю сообщение о том, что с ним желает встретиться руководитель крупной португальской экспедиции.