メキシコからの不法移民の取り締まり中に、黒いスーツを着込んだ二人が現れ、移民の一人を離れた場所に連れていきます。彼らはエイリアンの監視組織MIB(Men in Black)のメンバーで、移民の正体はエイリアンでした。エイリアンは、国境警備隊員に襲い掛かろうとしたためK(トミー・リー・ジョーンズ)が射殺しました。年寄りのDは、瞬時に対応できなかったことから引退を決意します。
一方、ニューヨーク市警の警察官ジェイムス(ウィル・スミス)は、超人的な脚力を持つ犯人を追い詰めましたが、「世界の終末が来る」と言い残して飛び降り自殺してしまいます。しかし、仲間はジェームスの話を信じない。Kはジェームスの力を買い、Dの後釜にスカウトします。宇宙難民のエイリアンが、今ではニューヨークに1500人ほど地球人の外見で住んでいて、大多数はまじめに働いていますが、中には危ない奴もいるらしい。
早速、指定区域外のエイリアンの調査に出動するKとL。多くのエイリアンが地球を脱出しようとしていることが判明します。違法進入したエイリアンが、「銀河」を管理するエイリアンを殺して銀河を手に入れようとしてるらしい。管理官の母星では銀河を返さなければ、地球を破滅させると迫ってきました。
死体置き場の検視官、ローレル(リンダ・フィオレンティーノ)は、運ばれてきた死体が地球人ではないということに気が付くたびに、Kによって記憶を消されていました。今回も管理官の死体から人間ではないことに気が付き、彼が飼っていた猫の首輪に銀河が隠されていることに気が付きます。エイリアンはローレルを襲い、銀河を手に入れると宇宙に逃亡しようとしますが、それに気づいたKとJも後を追います!!
もともとは今やDCと双璧をなすマーベル・コミックから生まれた話。だからといって、特殊能力を持った超人が登場するわけではありません。昔からUFOとか宇宙人の目撃談とかはたくさんあって、誰もがそんなこともあるかもしれないと思っていることを、一歩も二歩も進めたストーリーです。
気が付くとエイリアンは身近に人間の姿をして大勢生活していて、MIBは秘密裏に彼らの入出国と、地球での生活を監視・管理しているという設定が実にユニーク。まとめて宇宙人を引き受けてトラブルになるのが「第9地区」のような話ですが、ここでは一般人には知らせないことでパニックを防止し、平和な生活が維持されるという考え方。
ただし、全体のストーリーの流れはわかりにくいところがあって、そもそも猫の首にぶら下がっている「銀河」というものの正体や重要性があまり伝わってこないのが残念なところ。ラストシーンを見ると、どうやら宇宙人たちの遊び道具のボールのことらしい。このボールの中に銀河があり、太陽系があり、そして地球があって人類がいる・・・という一つの宇宙全体のことのことなんでしょうか。
何といっても、主役のトミー・リー・ジョーンズとウィル・スミスのコンビがいい。ロマンティストですが、冷静沈着なベテランKと、体力に自信ありの猪突猛進型のJという、いわゆる凸凹コンビが自然と楽しさを作り出しています。特殊メイクは、巨匠になったリック・ベイカーによるものでさすがです。一応、完結した雰囲気の終わりですが、大ヒット御礼により続編が登場しました。