The novel picks up soon after where Tarzan of the Apes left off. The year is 1910 and Tarzan is 22 years old. The ape man, feeling rootless in the wake of his noble sacrifice of his prospects of wedding Jane Porter, leaves America for Europe to visit his friend Paul d'Arnot. On the ship he becomes embroiled in the affairs of Countess Olga de Coude, her husband, Count Raoul de Coude, and two shady characters attempting to prey on them, Nikolas Rokoff and his henchman Alexis Paulvitch. Rokoff, it turns out, is also the countess's brother. Tarzan thwarts the villains' scheme, making them his deadly enemies.
Later, in France, Rokoff tries time and again to eliminate the ape man, finally engineering a duel between him and the count by making it appear that he is the countess's lover. Tarzan deliberately refuses to defend himself in the duel, even offering the count his own weapon after the latter fails to kill him with his own, a grand gesture that convinces his antagonist of his innocence. In return, Count Raoul finds him a job as a special agent in the French ministry of war. Tarzan is assigned to service in Algeria.
A sequence of adventures among the local Arabs ensues, including another brush with Rokoff. Afterward Tarzan sails for Cape Town and strikes up a shipboard acquaintance with Hazel Strong, a friend of Jane's. But Rokoff and Paulovitch are also aboard, and manage to ambush him and throw him overboard.
Miraculously, Tarzan manages to swim to shore, and finds himself in the coastal jungle where he was brought up by the apes. He soon rescues and befriends a native warrior, Busuli of the Waziri, and is adopted into the Waziri tribe. After defeating a raid on their village by ivory raiders, Tarzan becomes their chief.
The Waziri know of a lost city deep in the jungle, from which they have obtained their golden ornaments. Tarzan has them take him there, but is captured by its inhabitants, a race of ape-like men, and is condemned to be sacrificed to their sun god. To Tarzan's surprise, the priestess to perform the sacrifice is a beautiful woman who speaks the ape language he learned as a child. She tells him she is La, high priestess of the lost city of Opar. When the sacrificial ceremony is fortuitously interrupted, she hides Tarzan and promises to lead him to freedom. But the ape man escapes on his own, locates a treasure chamber, and manages to rejoin the Waziri.
Meanwhile, Hazel Strong has reached Cape Town where she meets Jane and her father, Professor Porter, together with Jane's fiancĂŠ, Tarzan's cousin William Cecil Clayton. They are all invited on a cruise up the west coast of Africa aboard the Lady Alice, the yacht of another friend, Lord Tennington. Rokoff, now using the alias of M. Thuran, ingratiates himself with the party and is also invited along. The Lady Alice breaks down and sinks, forcing the passengers and crew into the lifeboats. The one containing Jane, Clayton and "Thuran" is separated from the others and suffers terrible privations. Coincidentally, the boat finally makes shore in the same general area that Tarzan did.
The three construct a rude shelter and eke out an existence of near starvation for some weeks until Jane and William Clayton are surprised in the forest by a lion. Clayton loses Jane's respect by cowering in fear before the beast instead of defending her. But they are not attacked, and discover the lion dead, speared by an unknown hand. Their hidden savior is in fact Tarzan, who leaves without revealing himself, not realizing whom he was rescuing. Jane breaks off her engagement to William.
Later Jane is kidnapped and taken to Opar by a party of the Oparian ape-men who were pursuing their escaped sacrifice, Tarzan. The ape man learns of her capture and tracks them, managing to save her from being sacrificed by La. La is crushed by Tarzan's spurning of her for Jane.
Tarzan and Jane make their way up the coast to the former's boyhood cabin, where they encounter the remainder of the castaways of the Lady Alice, safe and sound after having been recovered by Tarzan's friend D'Arnot in another ship. "Thuran" is exposed as Rokoff and arrested.
Tarzan weds Jane and Tennington weds Hazel in a double ceremony performed by Professor Porter, who had been ordained a minister in his youth. Then they all set sail for civilization, taking along the treasure Tarzan had found in Opar.

Question: Where does Tarzan go to work for the French Ministry of War?
Answer: Algeria.