Однако этот план Лиссабона оказался трудновыполнимым на практике. Первая трудность состояла в том, что у португальцев не было товаров, которые бы пользовались спросом на восточноафриканском рынке. Там не было спроса на европейскую одежду, а индийские ткани и одежды продавали там еще до прибытия португальцев арабские купцы. Некоторые индийские ткани, награбленные в Килве или захваченные на мусульманских судах, были доставлены в Софалу, но местная фактория не могла постоянно работать только на ворованных товарах, и были предприняты большие усилия, чтобы наладить бесперебойную торговлю индийскими тканями с помощью султана Малинди.
С еще большими трудностями столкнулись португальцы при попытке контроля над Килвой и Софалой. Португальские власти неизбежно вошли в глубокий конфликт с традиционными правителями этих городов, лишившихся своего прежнего права выдавать торговые лицензии, разрешать продажу ряда товаров, назначать цены, взимать пошлины и в целом контролировать обширную и разветвленную торговую сеть, функционировавшую не только внутри Африки, но и в бассейне Индийского океана. В Килве португальцы надеялись решить эту проблему, посадив марионеточного правителя, но в 1506 г. вспыхнуло восстание, и купеческие семьи, боявшиеся потерять свою торговлю, ушли из города. К 1513 г. торговцы перестали приезжать в Килву, и португальцам пришлось покинуть свою факторию и разрешить вернуться в Килву семье прежнего султана.
После взятия и разграбления Момбасы Алмейда с попутным ветром проследовал в Индию. 13 сентября 1505 г. его флот достиг острова Анджедива. Там богатая добыча, захваченная в Момбасе, была в соответствии с действовавшим «морским кодексом» распределена между капитанами, моряками и солдатами. 22 октября флот Алмейды прибыл в Кананор. Королевский фейтор в этом городе Гонсалу Жил Барбоза настаивал на безотлагательном строительстве крепости, поскольку местный раджа без португальской поддержки был не в состоянии воспрепятствовать активной деятельности многочисленных мусульманских торговцев. К этому времени под властью мусульман находились Гуджарат, Дели, Берар, Биджадапур и великая империя Видждайанагар со столицей в Хампе.
В Кананоре Алмейду посетил посол индийского государства Нар-синга, которое препятствовало мусульманским завоевателям захватить юг Индии. Посол предложил Алмейде заключить союз против мусульман. После своей 150-летней борьбы против ислама Нарсинга видело в прибывших в Индию христианах естественных союзников. Адмирал быстро оценил важность миссии посла Нарсинги и решил принять его по-королевски. С этой целью он даже решил досрочно принять титул вице-короля Индии, хотя согласно королевской инструкции должен был сделать это лишь после завершения строительства трех крепостей (в Кананоре, Кочине и Коулане).
