1943. Vijf Amerikaanse soldaten zijn gestationeerd in Australië. Ze raken betrokken bij een geheime tijdreis missie van de OSS, de voorloper van de CIA. De soldaten worden 50.000 jaar terug in de tijd gestuurd om een buitenaards schip te zoeken, dat de geallieerden aan de overwinning tegen Hitler zou moeten helpen. De soldaten repareren hun tijdmachine, maar komen nu 300 jaar in de toekomst terecht. De nazi's hebben inmiddels de wereld veroverd en bereiden zich nu voor om God omver te werpen in de 25e dimensie. Hoe kunnen vijf ongelukkige soldaten de toekomst, het verleden en alles er tussenin ooit nog redden?
Even voor het ontstaan van menselijk leven op aarde ontdekt een groep apen een monoliet. Vier miljoen jaar later wordt een gelijkaardig object ontdekt op de maan dat een signaal uitzendt naar Jupiter. Commandant Bowman en astronaut Poole vertrekken op een speciale missie met het ruimteschip Discovery en de hulp van supercomputer HAL-9000.
In dit vervolg op 2001: A Space Odyssey wordt een Amerikaans/Sovjet-expeditie naar Jupiter gestuurd om uit te zoeken wat er mis is gegaan met de U.S.S. Discovery, terwijl de spanningen op aarde steeds groter worden. Enkele mysteries die de crew moet zien op te lossen zijn het verschijnen van een grote zwarte monoliet, en het lot van H.A.L., de boordcomputer van de Discovery.
