1 апреля флотилия ушла из Мозамбика на север. Не доверяя арабским лоцманам, Гама захватил у берега небольшое парусное судно и пытал старика, его хозяина, чтобы получить сведения, нужные для дальнейшего плавания. Через неделю флотилия подошла к портовому городу Момбаса (4° ю. ш.), где тогда правил могущественный шейх. Сам крупный работорговец, он, вероятно, почувствовал в португальцах соперников, но сначала хорошо принял чужеземцев. На следующий день, когда суда входили в гавань, арабы, бывшие на борту, в том числе оба лоцмана, спрыгнули в близко подошедшее доу и бежали. Ночью Гама приказал пытать двух пленников, захваченных у Мозамбика, чтобы выведать у них о «заговоре в Момбасе». Им связали руки и лили на голое тело кипящую смесь масла и дёгтя. Несчастные, конечно, сознались в «заговоре», но, так как они, естественно, не могли сообщить никаких подробностей, пытка продолжалась. Один пленник со связанными руками вырвался из рук палачей, кинулся в воду и утонул. Выйдя из Момбасы, Гама задержал в море арабское доу, разграбил его и захватил 19 человек. 14 апреля он стал на якорь в гавани Малинди (3° ю. ш.).
Местный шейх дружелюбно встретил Гаму, так как сам враждовал с Момбасой. Он заключил с португальцами союз против общего врага и дал надёжного старика лоцмана Ахмеда ибн Маджида, который должен был довести их до Юго-Западной Индии. Из Малинди флотилия вышла 24 апреля. Ибн Маджид взял курс на северо-восток и, пользуясь попутным муссоном, привёл суда к Индии – её берег показался 17 мая.
Вот так охарактеризовал роль ибн Маджида в экспедиции Васко да Гамы арабский учёный середины XVI в. Кутб ад-дин: «…Из тягостных необычных событий случилось [в конце XV в.] вступление проклятых португалов… в области Индии… И не проникал в Индийское море благополучно никто из их народов, пока… им не указал путь один искусный человек из моряков, которого звали Ахмед ибн Маджид. С ним завёл знакомство старший из… [них], которого звали Алмиланди [адмирал, т. е. Васко да Гама]. Он подружился с ним при пьянке, и тот, дойдя до опьянения, сообщил ему о дороге и сказал им: „Не приближайтесь к берегу у этого места Малинди, а углубляйтесь в море, потом обращайтесь к берегу Индии и вас не захватят волны“. Когда они так поступили, то стало спасаться от кораблекрушения много судов и количество их в Индийском океане увеличилось. Пополнения стали приходить к ним из Португалии, и они начали пересекать дорогу мусульманам, забирая в плен, грабя и захватывая насильно всякие суда…» (И. Крачковский).
Понятно озлобление автора, отражающее ненависть арабских купцов к их удачливым соперникам – португальцам; понятно и его желание объяснить опьянением (вероятно, выдуманным) ту помощь, которую араб ибн Маджид оказал врагам арабов. «В остальном же рассказ точно отражает историческую действительность, как она преломлялась в представлении обитателей берегов Индийского океана с его заливами» (И. Крачковский). Увидев индийскую землю, ибн Маджид отошёл подальше от опасного побережья и повернул на юг. Через три дня показался высокий мыс по-видимому гора Дели (у 12° с. ш.). Тогда лоцман обратился к адмиралу со словами: «Вот она страна, к которой вы стремились». К вечеру 20 мая 1498 г. португальские суда, продвинувшись к югу около 100 км, остановились на рейде против города Каликут (Кожикоде).