Procopius calls him "Hellestheaeus", a variant of Koinē Greek: Ελεσβόάς version of his regnal name, Ge'ez: እለ አጽብሐ ʾƎllä ʾAṣbəḥa (Histories, 1.20). Variants of his name are Hellesthaeus, Ellestheaeus, Eleshaah, Ellesboas, and Elesboam.
At Aksum, in inscription RIE 191, his name is rendered in unvocalized Gə‘əz as KLB ’L ’ṢBḤ WLD TZN (Kaleb ʾElla ʾAṣbeḥa, son of Tazena). In vocalized Gə‘əz, it is ካሌብ እለ አጽብሐ (Kaleb ʾƎllä ʾAṣbəḥa).
Kaleb, a name derived from the Biblical character Caleb, is his given name; on both his coins and inscriptions he left at Axum, as well as Ethiopian hagiographical sources and king lists, he refers to himself as the son of Tazena.
Procopius, John of Ephesus, and other contemporary historians recount Kaleb's invasion of Yemen around 520, against the Himyarite king, Yusuf Asar Yathar, known as Dhu Nuwas, a Jew who was persecuting the Christian community of Najran. After much fighting, Kaleb's soldiers eventually routed Yusuf's forces and killed the king, allowing Kaleb to appoint Sumuafa' Ashawa', a native Christian (named Esimiphaios by Procopius), as his viceroy of Himyar.
As a result of his protection of the Christians, Kaleb is known as St. Elesbaan after the sixteenth-century Cardinal Caesar Baronius added him to his edition of the Roman Martyrology despite his being a miaphysite. However, the question of whether Miaphysitism—the actual Christology of Oriental Orthodoxy, including the Coptic Orthodox Church of Alexandria)—was a heresy is a question which remains to this day.
Axumite control of Arabia Felix continued until c.525 when Sumuafa' Ashawa' was deposed by Abraha, who made himself king. Procopius states that Kaleb made several unsuccessful attempts to recover his overseas territory; however, his successor later negotiated a peace with Abraha, where Abraha acknowledged the Axumite king's authority and paid tribute. Munro-Hay opines that by this expedition Axum overextended itself, and this final intervention across the Red Sea, "was Aksum's swan-song as a great power in the region."
Later historians who recount the events of King Kaleb's reign include ibn Hisham, ibn Ishaq, and al-Tabari. Taddesse Tamrat records a tradition he heard from an aged priest in Lalibela that "Kaleb was a man of Lasta and his palace was at Bugna where it is known that Gebre Mesqel Lalibela had later established his centre. The relevance of this tradition for us is the mere association of the name of Kaleb with the evangelization of this interior province of Aksum."
Besides several inscriptions bearing his name, Axum also contains a pair of ruined structures, one said to be his tomb and its partner said to be the tomb of his son, Gabra Masqal. (Tradition gives him a second son, Israel, whom it has been suggested is identical with king Israel of Axum.) This structure was first examined as an archaeological subject by Henry Salt in the early 19th century; almost a century later, it was partially cleared and mapped out by the Deutsche Aksum-Expedition in 1906. The most recent excavation of this tomb was in 1973 by the British Institute in Eastern Africa.