A young Cambridge University professor, Horace Holly, is visited by a colleague, Vincey, who reveals that he will soon die. Vincey proceeds to tell Holly a fantastical tale of his family heritage. He charges Holly with the task of raising his young son, Leo (whom he has never seen) and gives Holly a locked iron box, with instructions that it is not to be opened until Leo turns 25. Holly agrees, and indeed Vincey is found dead the next day. Holly raises the boy as his own; when the box is opened on Leo's 25th birthday they discover the ancient and mysterious "Sherd of Amenartas", which seems to corroborate Leo's father's story. Holly, Leo and their servant, Job, follow instructions on the Sherd and travel to eastern Africa but are shipwrecked. They alone survive, together with their Arab captain, Mahomed; after a perilous journey into an uncharted region of the African interior, they are captured by the savage Amahagger people. The adventurers learn that the natives are ruled by a fearsome white queen, who is worshiped as Hiya or "She-who-must-be-obeyed". The Amahagger are curious about the white-skinned interlopers, having been warned of their coming by the mysterious queen.
Billali, the chief elder of one of the Amahagger tribes, takes charge of the three men, introducing them to the ways of his people. One of the Amahagger maidens, Ustane, takes a liking to Leo and, by kissing him and embracing him publicly, weds him according to Amahagger customs. Leo, likewise, grows very fond of her.
Billali tells Holly that he needs to go and report the white men's arrival to She. In his absence, some of the Amahagger become restless and seize Mahomed, intending to eat him as part of a ritual "hotpot". Realising what is about to happen, Holly shoots several of the Amahagger, killing Mahomed in the process; in the ensuing struggle Leo is gravely wounded, but Ustane saves his life by throwing herself onto his prostrate body to shield him from spears. All seems lost as the Amahagger resolve to kill Ustane along with the white men but Billali returns in the nick of time and declares that the three men are under the protection of She. Leo's condition, however, worsens and he nears death as Ustane faithfully tends to him.
They are taken to the home of the queen, which lies near the ruins of the lost city of K么r, a once mighty civilisation that predated the Egyptians. The queen and her retinue live under a dormant volcano in a series of catacombs built as tombs for the people of K么r. There, Holly is presented to the queen, a white sorceress named Ayesha. Her beauty is so great that it enchants any man who beholds it. She, who is veiled and lies behind a partition, warns Holly that the power of her splendour arouses both desire and fear, but he is dubious. When she shows herself, however, Holly is enraptured and prostrates himself before her. Ayesha reveals that she has learned the secret of immortality and that she possesses other supernatural powers including the ability to read the minds of others, a form of telegnosis and the ability to heal wounds and cure illness; she is also revealed to have a tremendous knowledge of chemistry, but is notably unable to see into the future. She tells Holly that she has lived in the realm of K么r for more than two millennia, awaiting the reincarnated return of her lover, Kallikrates (whom she had slain in a fit of jealous rage). Later, when Holly inadvertently and secretly discovers Ayesha in her hidden chamber, he learns that she may have some degree of power to reanimate the dead.
The next evening She visits Leo to heal him. But upon seeing his face, she is stunned and declares him to be the reincarnation of Kallikrates. She saves him and becomes jealous of Ustane. The latter is ordered to leave Leo and never to set her eyes on him again. Ustane refuses, however, and Ayesha eventually strikes her dead with magic. Despite the murder of their friend, Holly and Leo cannot free themselves from the power of Ayesha's beauty and Leo becomes bewitched. In explaining her history, Ayesha shows Leo the perfectly preserved body of Kallikrates, which she has kept with her, but she then dissolves the remains with a powerful acid, confident that Leo is indeed the reincarnation of her former lover.
In the climax of the novel, Ayesha takes the two men to see the Pillar of Fire, passing through the ruined city of K么r into the heart of the ancient volcano. She is determined that Leo should bathe in the fire to become immortal and remain with her forever, and that together they can become the immortal and all-powerful rulers of the world. After a perilous journey, they come to a great cavern, but at the last Leo doubts the safety of entering the flame. To allay his fears, Ayesha steps into the Spirit of Life, but with this second immersion, the life-preserving power is lost and Ayesha begins to revert to her true age. Holly speculates that it may be that a second exposure undoes the effects of the previous or the Spirit of Life spews death on occasion. Before their eyes, Ayesha withers away in the fire, and her body shrinks. The sight is so shocking that Job dies in fright. Before dying, She tells Leo, "Forget me not. I shall come again!"

Question: Where did Holly, Leo and Job travel to and become shipwrecked at?
Answer: East Africa
Alternative answer: Eastern Africa