Conan the Barbarian

This article's plot summary may be too long or excessively detailed. Please help improve it by removing unnecessary details and making it more concise. (January 2016) (Learn how and when to remove this template message)
Conan is the son of Corin, chief of a barbarian tribe. The youth is a skilled but violent warrior, who his father believes is not ready to wield his own sword. Their village is attacked by Khalar Zym, a warlord who wishes to reunite the pieces of the Mask of Acheron to revive his dead wife and conquer Hyboria. Thousands of years ago, the Mask, crafted by a group of sorcerers and used to subjugate the world, was broken into many pieces, which were scattered among the barbarian tribes. After locating Corin's piece of the mask, and murdering the entire village, Zym leaves. Conan, the only survivor, swears revenge.
Years later, Conan has become a pirate but still seeks revenge. He encounters a slave colony and frees it, killing all of the slave handlers in the process. In the city of Messantia, he encounters Ela-Shan, a thief being chased by a man whom Conan recognizes as Lucius, one of Zym's soldiers from years before. He allows himself to be captured alongside Ela-Shan. Conan escapes imprisonment, kills several of the guards, and confronts Lucius, forcing him to reveal that Zym seeks a girl, the pure-blood descendant of the sorcerers of Acheron; sacrificing the descendant and using blood from the body of the girl will unleash the mask's power. Conan helps the rest of the prisoners to escape, and, in gratitude, Ela-Shan tells Conan that, if he ever needs him, Conan will find him at the City of Thieves, Argalon. Lucius is then killed by the prisoners.
Zym and his daughter, the sorceress Marique, attack a monastery where they hope to find the pure-blood descendant. Sensing something is wrong, Fassir, an elderly monk, tells one of his students, Tamara, to run away and return to her birthplace. When Fassir refuses to reveal his knowledge of the descendant, Zym kills him. Marique also slays several of the priestesses. Tamara's carriage is chased by Zym's men, but Conan rescues her, kills three of her pursuers, and captures one of Zym's men, Remo. After forcing him to reveal Tamara's importance as the pure-blood, Conan catapults Remo into Zym's nearby camp, killing him.
Zym and Marique confront Conan, who pretends to be interested in exchanging Tamara for gold. Conan attacks Zym, but Marique assists her father by invoking soldiers made of sand, and poisons Conan with a poison-laced boomerang sword. Tamara rescues him and they return to Conan's ship, stationed nearby, where his friend Artus helps Conan recover. The boat is attacked by Zym's men, but although they kill several of Conan's men, they are defeated. Conan orders Artus to return to Messantia with Tamara and departs to confront Zym in his kingdom. Artus tells Tamara that Conan left a map behind and she follows him, meeting with him in a cave, where they have sex. The next day, as she is returning to the boat, Zym's men and daughter capture her.
Conan learns of Tamara's capture and departs to Argalon, where he asks Ela-Shan to help him break into Zym's castle unnoticed. Zym prepares to drain Tamara's blood, mending the mask. He plans to use the girl's body as a vessel for his wife's soul. After confronting an octopus-like monster that guards the dungeons and killing its handlers, Conan infiltrates Zym's followers, kills a guard, steals his robe, and watches as Zym puts on the empowered mask. Conan releases Tamara, and she escapes as he battles Zym, eventually reclaiming the sword Marique had stolen from his father. Marique attacks Tamara, but Conan hears Tamara's scream and defeats Marique, cutting off her hand. Tamara kicks her into a pit, where she is impaled. Zym swears revenge upon Conan.
Conan and Tamara become trapped on an unstable bridge as Zym attacks them. He uses the mask's power to call forth the spirit of his deceased wife, Maliva, a powerful sorceress who was executed by the monks from Tamara's monastery for attempting to unleash occult forces to destroy Hyborea, and Maliva's spirit begins to possess Tamara's body. She begs Conan to let her fall, but he refuses and instead destroys the bridge before jumping to safety with Tamara. The power-hungry ruler falls into the lava below the precipice crying out to his wife.
Conan and Tamara escape and he returns her to her birthplace, telling her that they'll meet again. He then returns to Corin's village and tells the memory of his father that he has avenged his death and recovered the sword Marique stole from him, restoring his honor.

Question: In what city does he encounter Ela-Shan?
Answer: Messantia