Lors de l'arrivée des Portugais en 1503, Zanzibar n'est qu'un gros village de pêcheurs occupé par des Hadimu, une ethnie aujourd'hui disparue. Ceux-ci en font un comptoir commercial sur la route maritime des Indes et, en 1600, ils y édifient un premier bâtiment en pierre : une église qui était située à l'endroit de l'actuel fort arabe.