Na obu swoich monetach, które zostawił w Aksum, a także w etiopskich źródłach hagiograficznych i jednym liście, król określił samego siebie jako syn Tazeny. Kaleb może być także Atsbyhą – jedną z postaci z późniejszej etiopskiej legendy.
Inwazja na Himjar Prokopiusz z Cezarei, Jan z Efezu i inni współcześni Kalebowi historycy wspomnieli w swoich dziełach o inwazji, jakiej ten dokonał w dzisiejszym Jemenie około 520 roku, przeciw zjudaizowanemu królowi Himjaru, o imieniu Yūsuf Thū Nuwās (يوسف ذو نواس), który był również znany jako Zu Nuwas (ذو نواس). Władca królestwa Himjaru prześladował chrześcijan w swoim królestwie, co zostało wspomniane w KoranieKoran LXXXV (surat al-burudż), wersety 4-8. W mieście Nadżran doszło do krwawej masakry wyznawców chrześcijaństwa. Po wielu walkach żołnierze Kaleba ostatecznie pokonali siły kierowane przez Zu Nuwasa i zabili go, co pozwoliło Kalebowi powołać chrześcijanina o imieniu Sumuafa Ashawa (Prokopiusz nazywał go Esimphaios), jako namiestnika Himjaru. W wyniku tej ekspedycji, mającej na celu obronę chrześcijan, Kaleb został później ogłoszony świętym o imieniu Elesban po tym, jak w XVI wieku kardynał Cezary Baroniusz umieścił go w edycji Martyrologium Romanum, mimo iż władca nie był katolikiem, tylko miafizytą.