The Queen of Attolia is the sequel to The Thief and the second book in the Queen's Thief series. It was originally published on April 26th, 2000 in the United States.
After Eugenides is captured spying in Attolia, the queen intends to have him executed. However, the Mede ambassador Nahuseresh convinces her to reconsider, and she instead decides to cut off Eugenides's right hand, the ancient traditional punishment for thieves. She then sends him back to Eddis.
While Eugenides is recovering, Eddis retaliates against Attolia, eventually escalating into open war between the two nations. Under the advice of the magus, Sounis also decides to go to war against Eddis, but quickly changes his mind after Eugenides tricks the king into believing that the magus is secretly working for Attolia. Sounis allies with Eddis and declares war on Attolia. The alliance lasts until Sounis discovers the truth about the magus, at which point the conflict becomes a three-way war.
Meanwhile in Attolia, Nahuseresh courts the queen in hopes that she will ally herself with the Mede and invite their armies onto the Little Peninsula, since the treaties between the Mede Empire and the Continent prevent them from otherwise landing troops there. Attolia responds positively to Nahuseresh's flirtations, but declines to formally treat with the Medes.
In an effort to prevent Attolia from allying with the Medes, Eugenides devises a plan to kidnap the queen and end the war. He takes a small force of Eddisian soldiers into Attolia along the Aracthus river, bringing with them fourteen fake wooden cannons. Eugenides uses the fake cannons to trick the queen into believing that Ephrata is under attack and, disguised as an Attolian soldier, he takes her away from the stronghold by boat.
Once they are away, Eugenides offers Attolia between death or marriage to him, thus ending the war. Eugenides professes his love for Attolia, but she disbelieves him, and accepts his proposal only for political reasons. They begin traveling to Eddis in order to negotiate the marriage contract, but are stopped by Nahuseresh, who has landed a small army of Mede soldiers in the queen's absence. The Eddisians surrender and Eugenides is taken as a prisoner back to Ephrata.
Although now freed from Eddisian captivity, Attolia ultimately decides to go through with the marriage to Eugenides. She expels the Mede army from her country and returns to her capital to begin negotiations with Eddis. The negotiations begin poorly, as the Attolian court generally regards the match unfavorably and Attolia continues to disbelieve in Eugenides's love for her . Eventually, it is revealed that Attolia was only able to capture Eugenides due to the interference of the goddess Moira. Infuriated, Eugenides demands an explanation from the Great Goddess Hephestia, and learns that the Sacred Mountain will one day erupt and destroy Eddis.
After Eugenides's confrontation with the gods, Attolia admits her own feelings for Eugenides, and finally begins to believe that he loves her as well.