Like its immediate predecessor, Tarzan Triumphs, the film mentions Tarzan's mate, Jane, but does not show her on screen. The explanation for her absence, as in the earlier film, is that she is still in the United Kingdom contributing to the war effort. (Maureen O'Sullivan had played Jane in the first six of Weissmuller's Tarzan films, but when the character of Jane returned after a two-picture absence, she was played by Brenda Joyce, not O'Sullivan.)
Tarzan receives a request from Jane, who is helping out on the British home front in World War II, to locate a rare plant-derived serum that can save the lives of many service members. He sets off into the Sahara, which is the shortest route to the place where the plants can be found. Boy and Cheetah tag along, and soon they are joined by a rambunctious horse and traveling magician Connie Bryce (Nancy Kelly), who has been entertaining Allied soldiers in the region.
The group travels to Connie's next destination, a small Arab kingdom in the desert. Tarzan intends to drop her off and continue his journey, not knowing that she is on a secret mission from Washington to thwart Nazi spies who have infiltrated the kingdom. Tarzan and Connie quickly run afoul of these devious agents, who manage to frame the two for crimes against the royal family. The apeman leads a daring escape with the help of Cheetah. Then, with the Nazis hot on their heels, the travelers head for the strange prehistoric jungle where the serum plants grow.