Returning from a mission from planet Cannibalon, Fry, Leela, and Bender announce their resignations to Professor Hubert Farnsworth. They reconsider when the Professor tells them he has scheduled a company vacation as thanks for not reporting him about his disregard for employee safety. He tells them the vacation is a cruise on the maiden voyage of the largеst space cruise ship ever built: the Titanic. No one suspects anything dangerous despite the crash/sinking of the first luxury ship to have that name. As they board, they are stopped by Zapp Brannigan, the honorary captain of the Titanic for its maiden voyage who attempts to seduce Leela again.
In an attempt to avoid Brannigan's unwanted advances, Leela claims she is engaged to Fry. On the way to their room, Bender meets the Countess de la Roca.
On the bridge, Brannigan diverts from the ship's original course and through a suicidally dangerous swarm of comets. At the buffet, Amy unexpectedly runs into her parents Leo Wong and Inez Wong who immediately attempt to set Amy up with a date, one who is very unsightly to her. In order to redirect her parents' attention, Amy claims Fry is her boyfriend.
At the ship's casino, Bender meets the Countess again and pretends to be rich to become her friend; at first he really wants her money and jewelry, until he realizes he loves her. Then she realizes he's broke after he steals a drinks from the bar, but she claims she still loves him.
In the swimming pool capsule, a limbo competition is being held. Hermes is urged to limbo, but declines, remembering a traumatic incident from twenty years ago. He was on the Earth Olympic limbo team, but during the 2980 Olympics, a boy ran onto the field, wanting to be just like his hero Hermes. He tried to limbo under an Olympic level bar but broke his spine. It is implied that the boy died. Hermes has never limbo-ed since then. Brannigan takes time off from steering the ship to judge the limbo contest, and declares Leela the winner, despite her not having entered "No matter, I know from personal experience just how horizontal you can get", Brannigan says. As a prize, she and Fry are invited to dinner at the captain's table.
At dinner both Zapp Brannigan and Amy's parents are present and demanding Fry kiss his date. Before the fake relationships can be exposed, Kif calls Brannigan back to the bridge. The new course has placed the ship in danger. Brannigan's attempt to correct the problem results in the ship flying toward a black hole. Realizing the danger he has put them in, Brannigan promotes Kif to Captain so that he can go down with the ship while Brannigan escapes. Bender heads off to save the Countess, while the rest of the crew make their way to the escape pods. On the way, an airlock door begins to close, blocking the crew's escape. Zoidberg holds it from closing all the way, but the door release is on the other side and no one can reach it. Hermes resurrects his old limbo skills to squeeze under and hit the door release. Arriving at the escape pods, they meet Amy's parents, who have found Amy a new boyfriend they feel is suitable: Kif. After waiting as long as they can for Bender, the crew launches the escape pod. Bender leaps from the Titanic, Countess in tow. He grabs the escape pod, but they are overweight. The Countess sacrifices herself to allow the others to escape. Bender is heart broken at the sad sight. As he gets inside, Fry consoles him, stating that it may be possible that the Countess is alive in another dimension; Farnsworth thinks not, as he confides in Zoidberg.