Construite sous le sultan hafside Abû Ishâq Ibrâhîm al-Mustansir (1349-1369), la porte s'appelle au départ Bab er-Rehiba ou « porte de la Petite esplanade ». Cette petite esplanade est une longue avenue reliant le palais de la kasbah aux parcs royaux de Ras-Tabia et d'Abou-Fîhr[1].
En 1435, la porte prend le nom de Bab El Allouj, lorsque le sultan Abou Amr Uthman fait venir d'Italie sa famille maternelle — une ancienne captive — et l'installe dans le quartier de l'esplanade, dans un palais que les Tunisois appellent alors Rabat El Allouj car le mot علج (allouj, au singulier alij), qui signifie « renégats » ou « infidèles », est l'appellation utilisée à l'époque pour qualifier les étrangers blancs, le plus souvent des esclaves chrétiens. La porte permet à cette époque de connecter le palais de la kasbah avec celui d'El Allouj[1]. Elle est détruite lors des travaux d'urbanisme lancés à la fin des années 1950[2].