故事设定在不远的将来（相对于1984年而言）1999年美国宇航局在月球表面发现了一个石碑，后又在木星轨道附近发现了同比例但更巨大的第二个石碑。2001年，派出前去调查的飞船发现号在任务期间因超级电脑故障导致船员伤亡，飞船和最后一位幸存者鲍尔就此失踪。
9年后的2010年，俄國太空總署長官找上因前次任務失敗而遭貶黜的佛洛伊德博士，聲稱已建造完成新的太空船，即將去探索漂流在太空中的發現號。由於整艘發現號及上面的哈爾超級電腦都是美國製品，所以希望伊德博士能參與任務重啟哈爾，或許能找到有用的資料。臨去前還意有所指的請佛洛伊德博士檢查一下軌道。
佛洛伊德博士發覺發現號的軌道改變，將會墜毀到臨近的星球上，因此找上自家長官示以利害。雖說美俄在當時政治氣氛下進行太空合作匪夷所思，但總不能讓俄國人帶走發現號上的資料獨自分析，美方必須介必入其中以令事有轉圜。終於成功讓長官去說服美國總統同意由美國人進俄方太空船執行任務。
任務過程中，佛洛伊德博士被提早解除冬眠狀態，因為太空船探得異常讀數。由於美俄兩方科學家各有顧慮，在討論這項發現所具的意義時小有不快，但終同意派出探測器作進一步探測。探測器探得若干結果後，隨即被不明物所毀，連帶震動太空船本身。佛洛伊德博士認為這是某種警告，不讓人類靠近。
科學家們終於靠近發現號及附近的巨石板開始調查。佛洛伊德博士主張以無人機器開始先期調查，但俄方指揮官堅持俄式大無畏精神，派出船員駕駛調查機器前往，終遭巨石板發出的強光吞噬。強光一路撲向地球。已成為星童的鮑爾，在地球上的親屬們都有異象。前妻在電視上看到前夫的影像向她告別，並表示稍後會有好事發生。深度昏迷的母親短暫清醒後，像見到久違的親人般高興異常。待護士趕到時，已因維生系統無故脫落而身故。
美俄科學家進入發現號重啟哈爾及一切系統。美方電腦科學家以蠕蟲消除哈爾關於殺人的記憶，並找出運作異常的原因。原來白宮下令哈爾對任務的真實目的向發現號的船員們保密。但電腦無法說謊导致逻辑错误。於是哈爾發展出偏執性格。
而在地球上，美俄兩國的軍事緊張關係加劇，已發展出多次小型衝突，雙方斷交，撤回己方人員，全面戰爭迫在眼前。美方科學家們接獲白宮命令，立即離開俄國領土，即載他們前來的太空船，回到美國領土，即發現號。待二十八天後，地球與他們的相對位置到達最短距離時，啟程回到地球。
佛洛伊德博士在發現號內接到不明來源不明身份者發來的訊息，要求他兩天之內立即啟程。佛洛伊德博士以為是己方的電腦專家在和他開玩笑，哈爾以各人的相對位置表明這不可能。於是佛洛伊德博士要求對方表明身份。對方自稱是已失蹤的鮑爾，並要求佛洛伊德回頭看。佛洛伊德博士回頭見到了鮑爾本人，並隨他到了外出艙。
鮑爾告訴他，很多事無法解釋，但所有人必須在兩天內離開。佛洛伊德博士急赴俄方太空船告知訊息。俄方指揮官當然不相信他，而且雙方太空船都沒有足夠的燃料飛回不在最短距離上的地球。佛洛伊德博士想出辦法，將兩艘太空船相連，以發現號的動力提供啟動力量，再由俄方太空船提供餘程所需動力。正當二人談論時，外頭的巨石板竟不知何時不知所踪。
大家同意立即啟程離開，所有人回到了俄方太空船。在發射倒數前，太家突然發現木星表面出現巨大漩渦，而且繼續變大，漩涡内充斥着与此前发现的巨型石碑一样的物体，数量有百万之巨。在發現號引擎啟動後，木星逐漸遭漩渦吞噬且縮小。待發現號用盡燃料到達極速後，俄方太空船太空船放掉發現號並開始以自身動力飛行。鮑爾的聲音出現在發現號，要求哈爾向地球發出最後的訊號。之後木星爆炸，成為第二顆太陽，發現號消失於其光芒中。地球自此有了第二顆太陽，再沒有黑夜，希望美俄兩國領導人受此啟發，走向和平。
鮑爾的最後訊息是：「所有星球都是你們的，除歐羅巴之外。不要企圖登陸。」歐羅巴在新太陽照耀下，由冰封的世界成為適居星球，並孕育出生命。
