Prince Paul is a tall man with blond hair and blue eyes. He wears a lavender jacket, white pants, black boots, black and white gloves, and a black cape with a red interior. His Cheka guise consists of a grey trench coat with a red scarf and a gray hat with a red star (symbolizing the Soviet Union).
He is accompanied by several mercenaries (most notably the incompetent Goofinov) and an unnamed raven.
Paul's real name is unknown.
Paul, a colonel in the Cheka (the Russian secret police) is out looking for Anastasia Romanov, the youngest daughter of Tsar Nicholas II, who has escaped the massacre of her family. He finds her in the abandoned Romanov palace, where he and his men attempt to capture Anastasia. Anastasia escapes with her magical instrumetns and flees for Copenhagen.
Paul pursues Anastasia to Copenhagen, where he assumes the guise of Prince Paul, a Russian royal who was murdered years ago. Here he successfully convinces everyone (including the Dowager Empress Marie) that he is the real prince. He arrives when Anastasia is presented to the White emigres (exiled Russians who had supported the White Army). Paul woos Anastasia, who immediately becomes infatuated with him.
Paul and Anastasia begin to spend much time together - dancing, dining, and sightseeing together. Vladimir Ichonovitch, the general who presented Anastasia to the emigres, becomes jealous. Paul sees Vladimir as a threat. When Vladimir is leaving the hotel that Anastasia is staying at, Paul (in his Cheka guise) orders his men to beat up Vladimir. Vladimir is thus unable to go with Anastasia when she faces the Dowager Empress.
The next day, Paul presents Anastasia to the Dowager Empress, who at first does not believe that Anastasia is the same Anastasia as her lost granddaughter. When Anastasia sings "In the Sun", a song that the Dowager Empress taught her as a child, the empress finally believes Anastasia and announces that Anastasia and Paul can finally be married. She reveals that Anastasia was bethrothed to Prince Paul when she was two years old. Anastasia agrees to the wedding.
Paul, seeing that his plans had fallen through, dines with Anastasia that night, wooing her. Anastasia says that she never remembers Paul being so kind . Paul responds "People change, Your Highness...people change", saying the last two words in a sinister tone. Paul's men break into the restaurant and carry Anastasia away. Paul does nothing, saying that he will rescue her when the moment is right.
When Anastasia is tied up and held hostage in a warehouse, Anastasia begs Paul to let her go. Paul refuses to help Anastasia, and reveals the truth to her - he is not a prince, but part of the Cheka, and has murdered the real Prince Paul. Paul then sings the song "Prince Charmless". Afterwards, he reveals that he intended to bring Anastasia back to Russia so she could be hanged,
Anastasia's accordion, Alexei, overhears this and rushes back to Vladimir and Anastasia's other three instruments. Alexei tells Vladimir that Paul is part of the revolution. Anastasia's instruments and Vladimir go to save Anastasia. The instruments fight Paul's men while Vladimir rushes upstairs, unties Anastasia, and convinces her that he had loved her from the start, while Anastasia convinces Vladmir that she loves him.Paul appears before Anastasia and Vladimir, telling them that he has nothing but contempt for both of them. He kicks Vladimir and points his gun at him. Vladimir lunges at Paul. The two of them fight and tumble across the floor, eventually rolling out the window. Anastasia tries to rescue Vladmir by asking for his hand, but he and Paul fall into the canal. Paul drowns, while Vladmir holds on to a rock.
With Paul dead, Anastasia is finally free from the Cheka. Her instruments then reveal that they are the spirits of her family, and they are able to revive Vladimir.
- He shares similarities to Prince Hans.
- Both pretended to fall in love with a princess just so they could overthrow them.