The film opens at a school where one boy is picking on another boy. We see Gracie Hart (Mary Ashleigh Green) as a child who beats up the bully and tries to help the victim (whom she liked), who instead criticizes her by saying he disliked her because he did not want a girl to help him. She promptly punches the boy in the nose and sulks in the playground.
We go forward in time to when Gracie Hart (Sandra Bullock) is working for the Federal Bureau of Investigation with Eric Matthews (Benjamin Bratt) as a Special Agent. On a mission, she does not follow orders from her superior and instead tries to stop their target from choking. Because of her actions, one of her squad gets shot, and she is put on a desk job.
The bureau receives a threat against the 75th annual Miss United States beauty pageant in San Antonio, Texas, from notorious domestic terrorist "The Citizen". Eric is elected to lead the mission to stop the attack. A computer search identifies Hart as the female FBI agent best qualified to go undercover as a contestant, although she pays little attention to her femininity.
Beauty pageant coach Victor Melling (Michael Caine), whose reputation was ruined after his last contestant criticized his methods, teaches the tomboyish Hart how to dress, walk, and act like a contestant. She is not used to such behavior, however, and sees the pageant and its participants as "outdated and antifeminist". Representing New Jersey as "Gracie Lou Freebush", Hart impresses the audience by playing the glass harp and demonstrating self-defense techniques during the talent competition. She unexpectedly becomes friends with the other contestants.
Several suspects exist, including corrupted competition director and former pageant winner Kathy Morningside (Candice Bergen); her unpleasant assistant Frank Tobin (Steve Monroe); veteran MC Stan Fields (William Shatner) who, like Morningside, is being replaced with a younger person; and Rhode Island's Cheryl Frasier (Heather Burns), possibly a radical animal rights activist. The Citizen is caught elsewhere, but Hart is beginning to suspect Kathy Morningside and is worried about the safety of the girls. She gives up her badge and gun and continues the investigation alone.
Matthews, after failing to support Hart, is about to leave for the bureau when he works out that Hart's suspicions were correct, and returns to help her. Hart surprises everyone, including herself, by becoming runner-up to Cheryl. The agents discover that Morningside and Tobin—secretly her son—impersonated Citizen due to her old grudge against the contest, and are attempting to murder Cheryl with a bomb in the title tiara. However, Hart and Matthews save the day, and they arrest Morningside and her secret son. Hart's fellow contestants choose her as Miss Congeniality, and she starts a relationship with Matthews.
- Sandra Bullock as Gracie Hart
- Mary Ashleigh Green as Young Gracie
- Michael Caine as Victor Melling
- Benjamin Bratt as Eric Matthews
- Candice Bergen as Kathy Morningside
- William Shatner as Stan Fields
- Heather Burns as Cheryl Frasier, Miss Rhode Island
- Steve Monroe as Frank Tobin/Morningside
- Ernie Hudson as Harry McDonald
- John DiResta as Agent Clonsky
- Wendy Raquel Robinson as Leslie Davis, Miss California
- Deirdre Quinn as Mary Jo Wright, Miss Texas
- Melissa De Sousa as Karen Krantz, Miss New York
- Asia De Marcos as Alana Krewson, Miss Hawaii
- Jennifer Gareis as Tina, Miss New York's girlfriend
- Cody Linley as Tough boy in flashback
- LeeAnne Locken as Kelly Beth Kelly, Miss Nebraska