ミス・アメリカ合衆国の美人コンテストへの出場から数週間後、FBI捜査官グレイシー・ハートは、銀行強盗を未然に防ごうと銀行内で張り込んでいたが、コンテストで顔が売れてしまったことから捜査官だと分かってしまい、張り込みは失敗する。グレイシーは有名になり過ぎて現場での仕事が出来なくなったことから、事務職かFBIの報道官になるかを選択することになる。ボーイフレンドで同僚捜査官のエリック・マシューズに振られた後、彼女は「FBIの新しい顔」としての地位を受け入れる。グレイシーと一緒に働くよう割り当てられたのは、シカゴから最近転勤してきたサム・フラーだが、彼女は他の人と一緒に働くのが苦手だ。
新しいスタイリストのジョエル・マイヤーズの助けを借りて、グレイシーはテレビに出演したり、ミス・アメリカ・コンテストへの潜入作戦に関する本を出版したりするなど、自分の新しい立場に取り組み始める。一方、コンテスト優勝者のシェリル・フレイジャーと司会者のスタン・フィールズはルーとカールのスティール兄弟に誘拐され、身代金を要求される。グレイシーは、誘拐事件が起きたラスベガスに行って記者会見をすることになる。彼女にはジョエルとサムが同行しており、サムは渋々グレイシーのボディガードを務めることに同意する。ラスベガスでは、支局長ウォルター・コリンズの意向に反して、グレイシーは独自に誘拐事件の捜査を開始する。彼女は、シェリルとスタンのリムジンの運転手が、誘拐に加担するために、ドリー・パートンのものまね芸人から報酬を得ていたことを知る。グレイシーは、その芸人を見つけて逮捕するが、それは本物のドリー・パートンであった。この事件はメディアの注目を集め、激怒したコリンズ支局長はグレイシーとサムにニューヨーク市に戻るよう命じる。