西暦2001年、月面で発見された謎の黒石板、モノリス解明のために、アメリカの宇宙船ディスカバリー号が木星へと旅立った。途中、コンピュータＨＡＬ9000が反乱を起こし、ボーマン船長（ケア・ダレー）を除いた乗組員全員を殺した。ボーマンは、モノリスが木星を回っているのを発見し「何てことだ。星がいっぱいだ」という言葉を残し行方不明となってしまった。そして2010年。ディスカバリー号の計画責任者で元アメリカ宇宙飛行学会議議長のヘイウッド・フロイド博士（ロイ・シャイダー）、ＨＡＬの生みの親チャンドラ博士（ボブ・バラバン）、ディスカバリー号を再生させる訓練を受けたエンジニアのカーノウ（ジョン・リスゴー）の3人は、ソビエトのタニヤ船長（ヘレン・ミレン）らと共に宇宙船レオーノフ号に乗り込み、木星へと向かった。世の中は、米ソ間の緊張が高まっていた。やがてディスカバリー号とのランデヴーに成功したところで、カーノウは宇宙遊泳してディスカバリー号に乗り移り、ディスカバリー号を再始動させた。そしてチャンドラ博士の手でＨＡＬが蛛る。いよいよ、木星軌道上でモノリスの調査の準備が始まった。しかし、モノリスに近づいたソビエトの隊員のポッドが吹き飛ばされてしまった。その頃地球では、米ソの関係が悪化し、いつ宣戦布告があってもおかしくない状況に陥っていた。ついにはディスカバリー号とレオーノフ号に米ソの隊員が分かれる命令まで下された。そんなある日、フロイド博士は、ボーマンの亡霊からの声を受けとった。その声は「あなたたちは2日以内にここを離れなくてはいけない」「すばらしいことが起ころうとしている」とくり返した。すると突然モノリスが姿を消し、同時に木星表面に見慣れぬ黒斑が生じて、それがだんだんと大きくなっていった。とはいえ、2日のうちに木星の軌道から遠ざかるのは燃料不足のため不可能だった。そこでフロイドは、2隻の宇宙船をつなぎ合わせ、地球に帰還するというアイデアを思いついた。そのためには、ディスカバリー号の点火をＨＡＬに任せねばならないが、ＨＡＬは最後まで木星の新現象を調査すべきだと主張した。結局、人間の命令を守るＨＡＬ。遠ざかるレオーノフ号の背後で、木星の黒斑は巨大化していった。観察では、黒斑と見えるものは分裂増殖する無数のモノリスであることがわかった。やがて、木星が閃光に包まれていった。いま、大宇宙の彼方からメッセージが、人類の前に姿を現わそうとしていた…。（ＭＧＭ／ＵＡ映画＝ＣＩＣ配給＊1時間53分）