Robert E. Howard set the story in Hyborian Africa. The Teeth of Gwahlur are legendary jewels, kept in the abandoned city of Alkmeenon, in the country of Keshan "which in itself was considered mythical by many northern and western nations".
Conan, following legends of this treasure, has travelled to Keshan and offered his services to train and lead Keshan's army against their neighbour, Punt. However, Thutmekri, a Stygian rogue with similar intentions, and his Shemitish partner, Zargheba, also arrive in the country with an offer of a military alliance with another of Punt's neighbours, Zembabwei, with some of the Teeth to seal their pact. The high priest of Keshan, Gorulga, announces that a decision on the matter can only be made after consulting Yelaya, the mummified oracle of Alkmeenon. This is all the treasure hunters require. Zargheba joins Gorulga in his expedition while Conan travels ahead of them.
In the abandoned city the initial atmosphere of the supernatural gives way to intrigue over the oracle. Zargheba has brought along a Corinthian slave girl, Muriela, to play the part of the oracle and tell the priests to hand all of the jewels to Thutmekri. Conan is first scared of the living oracle but quickly discovers the ruse. Intrigue and mystery follows as the imposter and the body of the genuine oracle switch and reappear. Gorulga, however, is an innocent in this, genuinely attempting to consult his oracle.
However, a fourth faction appears. A Pelishti traveller, Bit-Yakin, had visited the valley of the lost city in the past. When the people of Keshan visited the site to worship Yelaya as a goddess, Bit-Yakin provided prophecies from a hiding place. Eventually he died there; his undying servants buried him as per his instructions, and, got rid of their master's control, massacred all priests from Keshan who attempted to visit the city and consult the oracle afterwards. Bit-Yakin's servants, revealed to be large, gray-furred ape-like creatures, kill the survivors of Gorulga's party when they attempt to claim the jewels. Conan manages to acquire the chest containing the jewels but is forced to abandon them to save Muriela. They escape together and Conan ends the story by outlining a new plan.

Question: Where is this story set?
Answer: Hyborian Africa. 
Alternative answer: Hyborian Africa