The sixth-season premiere starts with a graphically upgraded Hypnotoad on screen, and Bender's voice announcing that people will forget the series was ever cancelled "by idiots" and later revived "by bigger idiots." Cutting to Planet Express. This is the first time the shorten theme was used. Fry walks in the lab where Farnsworth is and asks him why his hair is frizzy, also why he is covered in burns. Then the Professor explains what happened after the final movie ended. He explains that the wormhole they pass through to escaped Zapp Brannigan was actually the Panama wormhole, a sort-of "Comedy Central Channel" for shipping. Unfortunately, the Nimbus goes through too and began to fire on the Planet Express ship, damaging it. Fearing that they may crash, the crew activates their safety spheres. However, Farnsworth's sphere covered his whole body while everyone else's shielded only their heads, in which is because the professor was selfish. They then crashed, as well as the Nimbus, right by Planet Express, with only Fry and the Professor surviving, while everyone else became skeleton from the neck down. He drops them in the machine filled with stem cells, which he had plucked from healthy adults he had murdered himself, in an attempt to revive them. As a result, everyone comes out regenerated. Zapp is not dropped in and is still hanging but he is still alive despite having most of his body become a skeleton. Bender experiences difficulty with his rebirth, with his power supply being shot. Therefore, Farnsworth attaches his new doomsday device in Bender's chest cavity. However, the device's output is too powerful for Bender's body. He has to burn off the excess energy as fast as it's produced, like continuously partying, otherwise the energy will build up and he'll "explode and kill everyone here in a fireball of melted gears and splattered bowels!"
Fry then tries asking Leela out for a date, only to notice that she hasn't emerged from the birth machine. When she does, she doesn't wake up, even to the Professor's poking stick. Sadly, Leela is in an irreversible coma. Fry, depressed about Leela's state, goes to a Build-a-Bot store and builds a robot Leela. However, it doesn't act like her, so the Planet Express crew uploads her memories and appearance, taken from security camera footage. The robot Leela acts like her when she was last alive but soon finds out about her robotic nature when a hostile Nibbler takes a bite at her arm, exposing her wiring; she freaks out for an entire day. Uncertain about herself, robot Leela and Fry decide to just be friends.
After determining that the real Leela can't be wakened (due to repeated attempts with hitting and noise), the crew travel to the planet with the Cyclophage's preserve. Here, they attend Leela's funeral and read out her last will: her corpse is to be fed to the wild Cyclophage in the event of coma. As the beast approaches, Bender's incessant and inappropriate behavior, causes Leela to wake up to tell him to shut up. Leela is initially relieved, before she sees robot her and Fry kissing. After escaping from the Cyclophage, which latches onto their ship, they return to the base where the two Leela's confront each other and Fry. They both scold him and run away in anger. Later that night, Fry proclaims his true motive for returning Leela as a robot, while the real Leela listens on, hidden away. She forgives him, only to be interrupted by the Leela-Bot. The two Leelas fight each other, which the entire crew comes to watch. Amy passes Fry a ray gun to choose which Leela to shoot. Both Leela identify which one is which but Fry is slow on the uptake, at which they both call him an idiot. Fry then puts the gun down, refusing to shoot, only to accidentally shoot himself, revealing himself to be a robot.
The Professor explains Leela didn't die during the crash due to Fry's body shielding her. Farnsworth tossed his remains into the birth machine but nothing happened. Distraught, Leela built a Fry-bot. Unfortunately, the robot Fry experienced a malfunction due to Leela putting too much copper wadding in its stomach, resulting in it being burned and Leela being electrocuted, erasing both of their short-term memories. The Professor retrieved Leela's remains for rebirth, just as the robot Fry walked in on him.
It is then that the real Fry pops out of the machine. The robots then declared that they love each other and shed their skins and leave, speaking in Terminator-like voices. The real Leela is more confused over what just happened. Fry assures her that he will wait for her eventually. Bender decides he is fed up with constant partying and begins to vibrate with the excess energy. The Cyclophage suddenly emerges, and attempts to eat Leela. Bender's severe vibrations cause one of his eyes to fall out, and the Cyclophage swallows him, believing Bender to be a cyclops. The device explodes, killing the creature. Bender emerges intact and the Professor declares that Bender expended his excess energy. The crew leave in order to celebrate, and Zapp Brannigan emerges from the birth machine saying wheeee.