A finales del siglo XV, las coronas española y portuguesa comenzaban a repartirse el mundo. El comercio de las especias con las Indias era un bocado muy codiciado, aún en poder de los turcos otomanos.

En noviembre de 1497, el navegante portugués Vasco da Gama (1460-1524), comisionado por el rey Manuel I el Afortunado para abrir la ruta de las Indias, fue el primer europeo en doblar el Cabo de Buena Esperanza. Los portugueses arribaron a Mombasa el 7 de abril de 1498, donde los árabes les repelieron cortando sus anclas. La expedición continuó costeando y atracó en Malindi una semana más tarde. El navegante supo ganarse la confianza del sultán local, quien le proporcionó un piloto que conocía la ruta a Calicut (Kozhikode), el puerto comercial del sudoeste indio más importante de la época.

La expedición se hizo a la mar y arribó a la costa de Calicut el 20 de mayo, hecho que abrió por fin la ruta de las Indias para la corona portuguesa. Sin embargo, el navegante no alcanzó el éxito deseado en esta primera operación comercial: además de la hostilidad de los mercaderes musulmanes, el Zamorin (regidor hindú de Calicut) no apreció las mercancías que portaban los portugueses, muy apropiadas para el comercio en Africa Occidental pero de escasa demanda en la India.

La tensión crecía y Vasco da Gama tuvo que abandonar Calicut, y tras un viaje largo y penoso en el cual el escorbuto hizo estragos entre la tripulación, la expedición recaló en Malindi el 8 de enero de 1499, donde da Gama ordenó quemar su navío San Rafael al no disponer de suficientes marineros para gobernarlo.

La importancia estratégica de los puertos de la costa oriental africana indujo a la Corona Portuguesa a tomar el control de esta región. Durante diez años, la armada portuguesa asedió y conquistó todas las ciudades de la costa excepto su aliada Malindi. Mombasa ganó su reputación de ciudad rebelde al resistirse a la invasión, siendo destruida tres veces, en 1502, 1528 y finalmente en 1588, año en que definitivamente cedió al dominio portugués. La nueva metrópoli modificó las rutas comerciales del Índico, desviando el oro de Sofala alrededor del Cabo de Buena Esperanza hacia Europa.

La presencia de Portugal en la costa este de Africa se hizo duradera. Sin embargo, no existió una verdadera colonización, ya que la influencia no se extendió más allá de las posiciones militares. La herencia de Portugal se redujo a los nuevos cultivos importados de Sudamérica como el maíz, la mandioca, el anacardo, el tomate y el tabaco, además de algunas palabras portuguesas que aún hoy subsisten en el lenguaje swahili.

La nueva situación no acalló el deseo de los musulmanes por recuperar su dominio en esta región. El imperio turco otomano, en floreciente crecimiento tras conquistar Egipto y Arabia, envió a Alí Bey a Mombasa para incitar a los árabes de la costa a la rebelión contra los cristianos. La visita se repitió en 1588 con cinco buques. Mombasa abrió sus puertas a los turcos, que establecieron su cuartel general en la isla. Los portugueses, temiendo por su dominio, enviaron refuerzos desde Goa, en la India. La flota portuguesa llegó a Mombasa en 1590, al mismo tiempo que los Zimba, una tribu caníbal de la región del Zambeze que sembraba el terror en la costa. Los portugueses se aliaron con los Zimba y arrasaron la ciudad, entregándola después a los caníbales.

Temiendo nuevos ataques de los otomanos, en 1593 los portugueses decidieron construir la fortaleza de Fort Jesus en Mombasa, donde establecieron su capitanía general y trasladaron a su aliado el gobernador de Malindi, nombrándolo sultán de Mombasa. Pero las relaciones no fueron fluidas. El sultán fue asesinado en 1626 por orden del capitán portugués y sucedido por su hijo, don Jerónimo. Éste se rebeló contra los europeos en 1631 y exterminó a todos los portugueses refugiados en la fortaleza, excepto a cinco supervivientes. La presencia árabe creció de nuevo a partir de ese momento y Mombasa conoció un nuevo periodo de esplendor.

Entretanto, un nuevo poder crecía en el Índico, el de Omán. Los omaníes, establecidos en Muscat tras expulsar a los portugueses en 1650, comenzaron a relacionarse con los puertos de Africa Oriental hasta que el sultán de Omán decidió conquistar esta región. El 11 de marzo de 1696, siete navíos omaníes, fletados con un contingente de 3.000 soldados, entraron en el puerto de Mombasa. Los portugueses, avisados de la maniobra, habían reunido 2.500 hombres en Fort Jesus. Comenzó un largo asedio durante el cual los atrincherados en la fortaleza fueron diezmados por la peste bubónica. Al finalizar el año, sólo 50 sobrevivían. Sin embargo, consiguieron prolongar su resistencia durante casi dos años más hasta recibir refuerzos en septiembre de 1698. En diciembre de ese mismo año nuevos refuerzos llegaron a Mombasa, pero ya era demasiado tarde: el 13 de diciembre el sultán de Omán recibió noticia de que sólo restaban 20 personas en el fuerte, de las cuales sólo 8 eran soldados. Se produjo el ataque final y, tras 33 meses de asedio, Fort Jesus caía definitivamente en poder de Omán.

Años después, en 1728, Portugal haría un último y desesperado intento por recuperar Mombasa. El fracaso terminó para siempre con la presencia portuguesa en la costa de Africa Oriental.