Africa, the 1880s. Umbopa, the dispossessed King of the Kukuana people, is determined to return home and reclaim his throne. He poses as a guide and accompanies a group of English explorers on a perilous journey to his homeland, and the gold mines of King Solomon.

The explorers include Allan Quatermain, a pipe-smoking white hunter, Sir Henry Curtis, an aristocratic sportsman, and Captain Good, an eccentric, monocled, naval officer. They are joined by Kathy O'Brien, an Irish fortune hunter, who falls in love with Sir Henry Curtis.

On the journey Umbopa and the explorers have to cross a waterless desert, face a sandstorm, climb mountains and confront a hostile tribe. When they reach Kukuanaland, Umbopa reveals to the explorers his true identity, and takes charge of the expedition. The explorers support Umbopa in his battle to defeat the evil, one-eyed King Twala.

After the battle, Umbopa is restored to his throne, and in gratitude to the explorers he leads them to the gold mines of King Solomon. Umbopa has to rescue them when they are trapped in the mines by the ancient witch doctor, Gagool, believed to be hundreds of years old.

Umbopa becomes the proud king of an independent African country.