An American beautician named Joy Miller (Fran Drescher) teaches students to groom hair, but is put out of business when one of her students accidentally ignites hair spray with his cigarette, eventually leading to the school burning down. Joy ends up being highlighted in a newspaper article after she helps her students and the caged animals escape the building successfully.
The article is seen by Ira Grushinsky (Ian McNeice), a diplomatic representative of a small Eastern European country called Slovetzia (bordered by Hungary, Romania, and Ukraine), a country she never heard of. Ira has been sent to the United States to find a tutor for the three children of Slovetzia's President, and, mistakenly thinking that Joy is an academic teacher, offers the job to her. Joy accepts, and it is only after they arrive in Slovetzia that Ira realizes his error. By then it is too late, and Joy agrees to keep up the ruse of being a "real" teacher for the time being.
The initial meeting of Joy with the President, a dictator named Boris Pochenko (Timothy Dalton), gets off on the wrong foot, but Joy gets along well with his four children Yuri, Katrina (Lisa Jakub), Karl (Adam LaVorgna), and Masha (Heather DeLoach). Joy teaches them of life outside Slovetzia and helps them gain confidence in themselves. Joy frequently clashes with Pochenko, who is disturbed by her fierce independence and the fact that he cannot frighten her.
Joy's presence in Slovetzia is due to Pochenko's desire to change his reputation among other Western nations as a "beast". His second-in-command, Leonid Kleist (Patrick Malahide) is against Pochenko's "softening" strategy, and wants to crush the growing rebellion among Slovetzia's youth. Joy eventually learns that Katrina is in love with Alek (Timothy Dowling), one of the leaders of the youth rebellion. Alek is captured by Pochenko, but Joy secretly helps Katrina sneak to his cell to see him.
A summit of visiting emissaries are arriving in Slovetzia to meet with Pochenko, and Joy convinces him that the best way to prove that he is a modern-thinking man would be to throw a party. Joy is put in charge of preparations, and during this time she and Pochenko grow closer.
On the evening of the dinner, Joy confesses that she is not an academic teacher, but by this time Pochenko does not care about her credentials, only that she has brought happiness to him and his family. Later, Leonid confronts Joy with the fact that she has been helping Katrina meet Alek. When this information is brought to Pochenko, he argues with Joy on her meddling, and Joy decides to leave Slovetzia for good.
Some months pass. Leonid has quietly taken over administrative duties and signing sentences in Pochenko's name. Pochenko, made aware of this fact by Ira, confronts Leonid and strips him of his duties. Pochenko realizes that he has spent many months depressed and discontent after Joy's leaving, and decides that it is time to change his ways.
The film's final scene shows Joy back at home with her parents. She has also been depressed after leaving Slovetzia, but then receives a surprise visit by Pochenko. The pair reconcile