Hauria estat fundada per missioners musulmans al segle XII. La seva importància com a port comercial es confirmada per [[Al-Idrisi]] i per [[Ibn Said]], que descriuen Zeila com una ciutat considerable i centre del tràfic d'esclaus, i sota domini etíop. Pankhurst, entre d'altres, esmenta el relat de [[Marco Polo]] de què el sultà d'Aden (en realitat [[Adal]]) va capturar a un bisbe etíop i el va portar a Zeila, capital del soldanat, on va provar de convertir-lo per força i el va circumcidar segons la practica islàmica. Això va provocar la revenja de l'emperador etíop que va atacar la capital del soldanat i la va ocupar <ref>Pankhurst, p. 55.</ref>
[[Ibn Battuta]] va visitar Zeila el [[1329]], i la descriu com la ciutat més bruta, desagradable i pudenta de tot el monmón, i explica que els carrers estaven plens de restes de peixos i de la sang dels camell que mataven; diu que la ciutat estava tant revolucionada que va passar la nit al vaixell tot i que la mar estava agitada.<ref>Ross E. Dunn, ''The adventures of Ibn Battuta'' (Berkeley: University of California Press, 1989), pp. 122f.</ref> En aquest temps governava a Zeila la dinastia [[Walashma]] que també governava a [[Ifat]]. La ciutat va passar temporalment al Iemen,<ref>informació dubtosa, no contrastada </ref> però el [[1403]] <ref>el sobirà etíop David ho fou només fins vers 1411 i la conquesta hauria estat el 1403; però el fet es també atrubuït al rei Yeshak (vers 1411-1428) i llavors haria estat el 1415 </ref> tornava a estar en mans dels Walashma, perquè el sultà Sa'ad ad-Din II es va refugiar a Zeila davant l'atac de l'emperador etíop [[David I d'Etiòpia|David I]] (vers 1382-1411) o Yeshak (vers 1411-1428); el sobirà etíop va assetjar la ciutat i en va tallar el proveïment d'aigua fins que els defensors es van rendir; els etíops van entrar a Zeila i van matar al sultà; aquest sultà fou considerat un sant i la seva tomba fou venerada durant segles.<ref>Pankhurst, p. 57.</ref>
Pedro de Covilham, enviat del rei portuguès Joan II al negus, va arribar a Etiòpia després de desembarcar el [[1487]] a Zaila.
