Allan and his sidekick, the faithful and always amusing Hottentot Hans go on a mission for the Zulu wizard Zikali (who had previously appeared several times in the series) and endeavour to bring back some leaves from the rare Tree of Illusions.

As is usual in Haggard's novels, Heu-Heu starts off with an action set piece, a storm in which the heroes are forced to seek shelter in a Bushmen's cave, and from there moves swiftly and excitingly.

E. F. Bleiler's review of Heu-Heu states "while the lost-race aspects of the Walloo are somewhat stale, the descriptions of Black native life are, as always, fascinating"[2] It has been suggested that Heu-Heu influenced the script of the movie King Kong (by Merian C. Cooper and Edgar Wallace), which has a similar plotline.

Thomas has speculated that Heu-Heu influenced the ape-monsters of Robert E. Howard in the 1930s, in stories such as "Rogues in the House" and "Queen of the Black Coast".

[4][5] The motif of an ape-monster deified by a lost African tribe had appeared in a previous Quatermain adventure, The Holy Flower (1915).