The book is divided into four sections, each organized year by year to describe a key period of the life of Leo Africanus (originally named Hasan).

The book is based on life experiences that took Leo Africanus almost everywhere in the Islamic Mediterranean, from southern Morocco to Arabia, and across the Sahara. It places Hasan/Leo in various historical events and narrates those events. While filled with biographical hypotheses and historical speculations, the book offers a vivid description of the Renaissance world, with the decline of the traditional Muslim kingdoms and the hope inspired by the Ottoman Empire, as it grew to threaten Europe and restore Muslim unity.

Each section of the book is named after the city that played the major role in Leo's life at a given time: Granada, Fez, Cairo, and Rome.

• In Granada, the book illustrates the Granada War and the Treaty of Granada which marked the end of Islamic rule in Spain, as well as the Alhambra Decree which expelled all Jews from Spain.
• In Fez, Maalouf describes the news of the failed Muslim rebellion in Granada, the discussions resulting in the Oran fatwa, the Spanish and Portuguese colonial campaigns in North Africa and their conflicts with the North African Muslims.
• In Cairo, it depicts the Ottoman–Mamluk War which ended in the Ottoman conquest of Egypt.
• In Rome, the narration includes an Ottoman embassy to France, the Italian War of 1521–26, and the War of the League of Cognac, culminating in the 1527 Sack of Rome.

• Hasan ibn Muhammad al-Wazzan, later known as Leo Africanus, the titular character and the narrator of the book.
• Muhammad al-Wazzan, Hasan's father, a weighmaster in the Emirate of Granada.
• Salma, Hasan's mother and Muhammad's Arab wife.
• Warda, Hasan's stepmother and Muhammad's Castilian wife.
• Abu Marwan or Khali, Hasan's maternal uncle and a diplomat and statesman in the Kingdom of Fez.
• Harun the Ferret, Hasan's closest friend in Fez and later known as Harun Pasha, a diplomat with the Ottoman Empire.
• Hiba, a Numidian slave girl gifted to Hasan by an African lord, as well as Hasan's romantic interest.
• Nur, a Circassian princess and the widow of Selim I's rival claimant of the Ottoman throne, whom Hasan married in Cairo.
• Pope Leo X, Hasan's master after he was captured and enslaved. Later he freed Hasan and baptized him John-Leo.
• Francesco Guicciardini, an Italian statesman and one of Leo's friends in Rome.
• Julius de' Medici, later Pope Clement VII, Leo's benefactor after the death of Leo X.
• Abbad the Soussi, a merchant who was captured together with Hasan, and later became known as Master Abbado, a successful merchant in Naples, and Leo's friend in Italy.

• "On a Camel Moving Forward in Time" (a review of Amin Maalouf, Leo Africanus. Norton, 1989), The New York Times Book Review, March 12, 1989