Durante uma entrega da Planet Express, Amy encontra-se secretamente com Kif, que então pede a ela para desistir do emprego em favor do relacionamento. Amy, porém, afirma não estar pronta para tanto. Mais tarde, Dr. Zoidberg diagnostica a gravidez de Kif e logo descobre-se que a mãe é Leela, por simplesmente haver tocado a pele de Kif durante seu período fértil. Amy também não se sente preparada para a maternidade e Kif, decepcionado, volta a seu planeta natal para dar à luz no mesmo pântano em que nasceu.

Quando Bender começa a descartar lixo nuclear nos esgotos da cidade, desperta a ira dos mutantes, que então o arrastam, com Fry e Leela, aos subterrâneos para serem convertidos à força em mutantes. Durante a tentativa de fuga dos três, Leela faz uma incrível descoberta sobre sua verdadeira ascendência, finalmente encontrando os pais pela primeira vez.

Bender se apaixona pela nova personalidade feminina do computador de bordo da nave Planet Express. Enquanto isso, Fry procura por um coração de açúcar com a frase que melhor expressa seus sentimentos por Leela.

Um creme misterioso e milagroso do Dr. Zoidberg confere poderes especiais a Fry e Leela, que formam com Bender uma equipe de super heróis conhecida como "Novo Time da Justiça" ("New Justice Team"). Ocultos sob as identidades secretas de "Capitão Ontem" (Fry), "Clobberella" (Leela) e "Super Rei" (Bender), os três passam a combater o crime pela cidade, mas Leela descobre que suas novas obrigações como super heroína podem criar sérios problemas em seu relacionamento com os pais.

Quando o Dr. Zoidberg devora publicamente a bandeira da Terra durante as comemorações do Dia da Liberdade, é sentenciado à morte por seu comportamento anárquico. Porém, antes que a sentença lhe seja aplicada, os Decapodianos (raça à qual Zoidberg pertence) invadem a Terra para ajudá-lo, ensinando à população terráquea o verdadeiro significado da palavra "liberdade".

A produção da novela "Todos os Meus Circuitos" ("All My Circuits") promove um concurso para substituir o robô no papel de filho de Calculon. Bender, sabotando o teste, acaba sendo escolhido e em pouco tempo, seu comportamento reprovável em cena se torna uma influência negativa para as crianças. Quando telespectadores revoltados formam um grupo de protesto intitulado "Pais Contra a Grosseria na TV" ("Fathers Against Rude Television" ou "F.A.R.T."), Bender conclui que seu lugar não é na televisão.

Fry descobre que a pizzaria onde trabalhava está sendo exibida como maravilha arqueológica do século XX em um museu. Entre os artefatos da mostra, Fry encontra o fóssil de seu cachorro Seymour e, após discussões com o curador do museu, consegue levá-lo para casa. Logo o Professor Farnsworth afirma ser capaz de trazer Seymour novamente à vida por meio de clonagem e Bender começa a sentir muitos ciúmes de sua amizade com Fry.

O tradicional método de despejar toneladas de gás clorofluorcarbono nos vasos sanitários para contrabalançar os efeitos do vazamento de Freon para a atmosfera falha e Al Gore convoca uma conferência em Estocolmo para tratar do assunto. Durante os debates, o Professor Farnsworth confessa que sua negligência em criar robôs que vazam gás CFC foi a verdadeira responsável pelas mudanças climáticas e a destruição de todos eles é apontada como única solução. Bender, resignado, reúne-se a outros companheiros nas ilhas Galápagos.

A equipe da Planet Express conclui que, aos 161 anos de idade, o Professor Farnsworth está velho demais e decide presenteá-lo com um tratamento de rejuvenescimento em um spa. O tratamento funciona e ele retorna aos 53 anos, mas devido a um acidente no processo, toda a equipe acaba voltando à adolescência também. Mais tarde, enquanto o Professor busca um meio de devolver todos à idade original, os novos adolescentes aproveitam a vida e Leela tem a chance de experimentar um relacionamento diferente com seus pais.

Fry não consegue impressionar Leela e fica arrasado quando ela recusa seu convite para um jantar. Piorando as coisas, Leela resolve sair com Chaz, auxiliar do prefeito. Sentindo-se inútil e o maior dos perdedores, Fry acaba sendo levado por Nibbler em uma missão para salvar o universo dos planos malignos dos cérebros voadores e descobre no processo seu real valor, além da verdade sobre os fatos ocorridos na noite de 31 de Dezembro de 1999, quando foi criogenicamente congelado.

Fry lidera a tripulação da Planet Express em uma missão através da galáxia para recuperar os 79 episódios proibidos de "Star Trek: A Série Original", em que encontram o elenco original da série mantido em cativeiro por um ser de energia obsessivo e infantil de nome Melllvar.

O Professor Farnsworth envia Leela, Bender e Fry em uma perigosa missão para coletar mel produzido por ferozes abelhas espaciais. Durante a tarefa, Leela interessa-se por um filhote de abelha rainha e o leva consigo na nave, mas o animal acaba se enfurecendo e ferindo gravemente Fry, que falece logo em seguida. Leela, devastada pelos sentimentos de culpa e tristeza, experimenta uma gradual perda de contato com a realidade.

Para competir na divisão de robôs femininos dos Jogos Olímpicos de 3004 ("3004 Earth Olympian"), Bender disfarça-se de "Coilette de Robonia". No entanto, ao saber que precisará ser examinado para validar suas vitórias, ele pede ao Professor Farnsworth uma operação de mudança de sexo. Quando Calculon apaixona-se perdidamente por "Coilette de Robonia", Bender finalmente conclui que precisa reverter a cirurgia antes que seja tarde demais.

O Professor Farnsworth adquire um novo modelo de robô, o 1-X, exibido durante a feira de tecnologia Roboticon 3003. Em função de sua inferioridade técnica, Bender percebe que seu emprego na Planet Express está ameaçado e, seguindo uma sugestão do Professor, retorna à MomCorp para uma atualização. Porém, temendo perder sua personalidade, foge para uma ilha tropical, onde encontra outros robôs obsoletos avessos à tecnologia e ganha modificações realmente especiais.

O Professor Farnsworth proíbe que a equipe da Planet Express olhe dentro de uma misteriosa caixa. Leela, no entanto, não consegue resistir à tentação e descobre que a caixa é na verdade um portão para um universo paralelo e com outra turma do Planet Express.

O presidente Richard Milhous Nixon, satisfeito com os resultados da vitória de Zapp Brannigan sobre as aranhas do planeta Tarantulan 6, distribui um bônus de 300 dólares a cada habitante da Terra. Os membros da Planet Express decidem gastar suas respectivas partes em dinheiro de modos diferentes. Mais tarde, durante um jantar comemorativo, Fry, com excesso de cafeína no sangue, salva todos de um grande incêndio; Dr. Zoidberg oferece um farto banquete e Bender é preso por roubar um valioso charuto.

Durante uma excursão, a equipe da Planet Express acampa na Floresta Nacional de Duraflame. À noite, Fry sai de sua barraca em busca de um suposto pé-grande, mas acaba sendo abduzido. Na manhã seguinte, ele percebe que teve o nariz roubado. A TV noticia que outros também passam pelo mesmo problema e que alienígenas caçam narizes humanos para usar como afrodisíaco. Leela, Bender e Dr. Zoidberg unen-se a Fry na busca por seu nariz, que encontram nas mãos de Lrrr, líder do planeta Omicron Persei 8.

Fry, em segredo, faz aulas de holofone na esperança de impressionar Leela. No entanto, suas habilidades não são suficientes e a única saída que vislumbra, seguindo uma sugestão de Bender, é trocar de mãos com o Demônio Robô. Graças ao pacto, Fry torna-se um músico de grande sucesso e decide montar o espetáculo "Leela: Órfã das Estrelas". O Demônio Robô aparece na estréia da peça e, em uma sucessão de atos ao estilo de uma autêntica ópera, acaba pedindo a mão de Leela como pagamento. Fry se recusa a aceitar e desfaz a troca, voltando a tocar mal o holofone com suas próprias mãos. Insatisfeito, o público abandona o teatro, mas Leela, emocionada, pede para que Fry conclua a peça.