There’s a little corner of my African childhood home I remember the most clearly. Like most properties on the outskirts of Salisbury, in the British colony of Rhodesia (now Harare, Zimbabwe), ours had servants’ quarters: a white, two-bedroom, iron-roofed cottage, where our nanny, Ida, and gardener, Lazarus, lived. In front of their house was a fence that demarcated our territories: our manicured suburban garden in which we tumbled about all day, swinging on ropes, climbing trees, chasing dogs, collecting lizards, insects, snakes. And, in the corner, their little bit of Africa.

There was nothing particularly unique about their patch – it was a wild square of red earth, crawling in the pumpkins they cultivated, and rows of maize, with lines of washing fluttering nearby – but it was my favourite part of the garden. It was their private space (so forbidden), it was muddy, and, most important of all, there was always a fire burning inside a ring of stones on the earth: boiling up a soot-blackened enamel kettle or pot of sadza (maize-meal porridge), and spewing smoke that made my skin and hair smell of Africa.

It was here, when my mother was at work, that my brother and I got our first African education. We learnt how to make a fire, to balance a bucket on our heads with water for the kettle. And, most importantly, it is where we heard our first African tales.

Stories have been told orally for centuries in Africa – not just as entertainment and to pass away the evening hours in winter, when the crops were harvested and times were good, or to perpetuate an historical event, but as moral lessons to teach children right from wrong and good from bad. There are hundreds of them all over the continent, telling of magic and ogres, princes and talking animals, wicked spirits and mischievous creatures, stories that have travelled with tribes as they wandered through Africa. So, throughout my life, wherever I’ve been I’ve hunted them down: on camping trips, safaris and, as a journalist, on stories all over the continent.

The older I got, though, the more difficult it became to find them. They were disappearing. Radios, and in some villages televisions, had started to replace traditional gatherings. Western literature, and pictures of Janet and John, rather than hyenas, elephants and lions, were becoming commonplace in rural classrooms. Old women had to turn their energies to bringing up Aids orphans, rather than sitting round fires telling stories. At one school I visited in Kwekwe, Zimbabwe, there was not a single eight-year-old child who could remember a traditional story to tell me. Spurred on by African friends, by old ladies who had dreamt of their stories being preserved, by teachers who said they would love local publications for children to read, by Shona historians at the University of Zimbabwe and by the Somalian model Iman, who told me she had searched New York bookshops for traditional African stories to read to her daughter, I decided to set off on a journey to attempt to preserve them.

I am not the first person to attempt to do so. An afternoon in Harare’s archives – an extraordinary collection of colonial papers, books, and photographs – unearthed documents written in the 1800s by missionaries, describing “ungodly, Satanic myths”. Aesop was inspired by them; Rudyard Kipling adapted them. In South Africa’s libraries, I discovered compendiums written as early as 1929, gathered by early settlers, in Harare’s near-empty bookshops, I discovered a few single stories, but there were few, if any, modern compendiums collected orally from villagers themselves.

That was my challenge. And in 2003, I set off to Africa.

I had no real plan, other than basing myself at my mother’s house in Harare, and certainly no idea how I was going to manage to find the stories, but they slowly emerged, as I took packed local buses, hitched rides with hunters on tiny planes, and got lifts in cars through Zimbabwe, Zambia, Botswana and South Africa, and put word out, through anyone who would listen, of what I was looking for. Once the bush telegraph started working, all sorts of people emerged: men whose grandmothers were the village storytellers, old peasant farmers who couldn’t tell me how to spell their names because they’d never been taught to read or write, Bushmen keen to relate lurid sexual fables, a renowned local poet, teachers in rural schools, farm workers.

Because almost everyone I met, it seemed, loved these stories and wanted them to be preserved for future generations, I was greeted everywhere with the greatest hospitality. Farmers in Zambia passed me round from farm to farm. Game guides put me up in huts. Jack’s Camp, in the Kalahari in Botswana, gave me a tent and sent me out into Bushmen communities with one of their trackers. A former Zambian headmaster in his eighties walked from village to village with me, with his stick, introducing me to old women. I didn’t eat a single meal on my own.

Naturally, often when I arrived at a village, alone, I was treated with some suspicion. It was my Dictaphone and cameras that opened doors. Once I’d found someone who spoke English to translate for me, and let villagers hear what I had already gathered on tape and see pictures of other storytellers, there would be great enthusiasm. Most had never seen a tape recorder, so for the first half hour or so, I’d encourage them to talk into it, then play their own voices back. With often dozens of jostling children trying to get the best view, I would show photographs on my camera, and take shots of them, which they’d stare at, wide-eyed.

Then we could begin business. I would be sat down – usually round a fire on a rock or wooden stool, surrounded by dozens of inquisitive children and villagers – and for hours, be regaled with story after story, new storytellers joining in and volunteering their tales. Often they would leap about, scream, mimic animals, whistle and dance. Some would sing. Always, though, they’d be listened to, with awe, as men, women and children stopped everything to hear stories: of magic rivers, of talking crocodiles, of thunderous gods in the sky, of wicked animals – and of morals, morals that often would be repeated until everyone was clear what the lesson was.

Three months later, I had ten 120-minute audio tapes, and about 200 stories in 20 different languages, in a box in my backpack. I had a digital camera packed with portraits of storytellers. I had a laptop brimming with translations from villagers who had helped me along the route, sitting with me under trees listening to my tape recorder and, line by line, translating the stories I had just been told into English, as I typed them on to my laptop.

Explore Books

• Book Extracts

• Book Reviews

• Books Group

• Audio Books

Times Recommends

• The Sunday Times 100 best holiday reads
• What will we be reading this summer: the booksellers predict
• Literary festivals: a survivor’s guide