While visiting Vienna incognito, Russian Grand Duke Peter (Robert Young) is lured away from a masquerade ball by the beautiful Maria (Maureen O'Sullivan), only to find himself the prisoner of Polish nationalists. Peter is made to write a letter to his father, the Czar of Russia, offering to exchange him for Maria's father, who has been sentenced to be executed.
Because their previous petitions for clemency were intercepted and never reached the Czar, the Poles task secret agent Baron Stephan Wolensky (William Powell) to deliver the letter. Meanwhile, Colonel Pavloff (Frank Reicher), head of the Russian secret police, assigns his own agent, Countess Olga Mironova (Luise Rainer), to take to Russia documents incriminating Wolensky as an enemy agent, along with an order for his arrest.
Since he is already going to Saint Petersburg, Wolensky's friend, Prince Johann (Henry Stephenson), asks him to deliver a pair of ornate candlesticks to a princess. Each of the candlesticks has a secret compartment, so the baron secretly places the letter in one. Later, when Prince Johann amuses Countess Mironova by showing her the candlesticks' unusual feature, she puts her documents inside the other, and persuades the prince to entrust the pair to her. When Wolensky is given the news, he sets off in pursuit.
A complication arises when Mironova's maid, Mitzi Reisenbach (Bernadene Hayes), and Mitzi's lover Anton (Donald Kirke) steal her jewelry and the candlesticks. As they trace the candlesticks, first to Paris and then to London, Wolensky and Mironova admit to each other that they are on opposite sides, but this does not prevent them from falling in love.
Finally, the candlesticks are put up for auction. The countess places the winning bid, but since only cash is acceptable as payment, she does not have enough to pay for them. The baron solves the problem by offering to pool their resources, each getting one candlestick. Wolensky chooses what he believes is the one with his letter, but he picks the wrong one. He finds and reads his own death warrant. When Mironova tries to exchange candlesticks, Wolensky declines. She then offers to deliver both sets of documents, while Wolensky remains safely outside Russia. He does not trust her, but knowing the price of her failure, offers to give her back her papers once he has safely delivered Peter's letter.
Meanwhile, the Polish patriots become restless at the long, unexplained delay. Korum (Douglas Dumbrille) favors killing Peter, but Maria persuades the others to wait until they hear from Wolensky. Peter eavesdrops and is pleased. The Czar pardons and releases Maria's father in exchange for his son.
In St. Petersburg, Pavloff arrests Miranova at her mansion. When Wolensky shows up there with her documents, she tosses them into the fireplace. Pavloff takes them both before the Czar. The ruler of Russia graciously frees the loving couple, who decide to marry.
According to MGM records the film earned $733,000 in the US and Canada and $600,000 elsewhere resulting in a profit of $259,000.