It's the year 3028 and Professor Sam Tucker (voice of RON PERLMAN) and others have developed the Titan project, a testament to the human spirit and something an alien race, the Drej, fears and wishes to destroy. As such, they arrive at Earth and destroy the planet, but not before Tucker sends his five-year-old son, Cale, on an escape craft with his associate Tek (voice of TONE-LOC), while he successfully manages to leave on the Titan.
Fifteen years later and with Earth gone, the abandoned Earthlings are scattered about the universe, nothing more than an endangered species. Cale (voice of MATT DAMON) is now a young and disillusioned man working on a salvage vessel, having to cope with alien hostilities and a less than hopeful future.
That all changes when he's approached by Korso (voice of BILL PULLMAN), the charismatic captain of the Valkyrie, who informs Cale that he's been searching for the young man for some time to tell him of his mission in life. It seems that Cale has a genetically encoded map on his hand that, once activated, points to the hidden location of the Titan, a spaceship containing a device that's humankind's last chance of survival.
Accompanied by Akima (voice of DREW BARRYMORE), the no-nonsense human pilot of the Valkyrie who grew up on a drifter colony, along with Preed (voice of NATHAN LANE) Korso's sly alien first mate; Gune (voice of JOHN LEGUIZAMO), the ship's squirrelly alien navigator who must decipher the map, and Stith (voice of JANEANE GAROFALO) the cranky alien gunner, Cale and Korso set out to locate the Titan. Along the way, however, the crew must contend with repeated attacks by the Drej as well as traitors within their own ranks as they try to go about saving humankind.