[2] Writing in The Observer, Zoë Heller described Mahjoub's first novel, Navigation of a Rainmaker (1989), as providing "a rich picture, both of Africa's vast, seemingly insuperable problems – and of the moral dilemmas faced by a well-meaning, ineffectual stranger".
[4] Wings of Dust (1994), Mahjoub's second novel, explores the legacy of the first generation of Northern Sudanese who were educated in the West in the 1950s and inherited the task of creating the newly independent nation.
[6] The Carrier (1998) is split between the early 17th century and present-day Denmark, where an archaeological find reveals a link to a visitor from the Arab world in medieval times.
[7] In The Drift Latitudes (2006), Rachel, following the death of her son, becomes aware of the existence of a half-sister, Jade; the product of a relationship her father had late in life.
The novel uses a mixture of fable and multiple characters to describe events around the evacuation of Nubian villages as a consequence of the raising of the Aswan High Dam.
In 1993, "The Cartographer's Angel" by Mahjoub won a one-off short story prize organised by The Guardian newspaper in conjunction with the publisher Heinemann Books, judged by Adewale Maja-Pearce, Margaret Busby and Ian Mayes.
Mahjoub subsequently began a UK-set series of crime novels featuring detective Drake and forensic psychologist Crane, the first entry of which was The Divinities (2019).