The story is divided into four acts, each set on November 2 in four consecutive years. Manuel “Manny” Calavera works as a travel agent at the Department of Death in El Marrow, where he is trying to pay off a debt. He is frustrated by being assigned clients who must take the four-year journey and is threatened by his boss, Don Copal, if he does not improve his results.

Manny steals Mercedes “Meche” Colomar from his co-worker Domino Hurley after the department’s computers assign her to the long journey. He believes she should have a place on the “Number Nine” luxury express train because of her pureness of heart. After sending her on her way, he discovers that Domino and Don have been rigging the system to deny many clients Double N tickets and save them for Hector LeMans, who then sells them at a high price.

With help from his driver Glottis, Manny searches for Meche in the Petrified Forest and meets Salvador “Sal” Limones, leader of the Lost Souls Alliance, who recruits him. Manny later reaches Rubacava, where he finds he has arrived before Meche and waits for her to appear.

A year later, Manny is running a nightclub in Rubacava and learns that Meche was seen leaving with Domino. The search leads him to a coral mining plant at the Edge of the World, where Domino is holding Meche and other stolen-ticket clients as slave labor. After rescuing them, Manny and his companions escape, and the story continues as they travel toward the Ninth Underworld.