Rimmer is eagerly relating the story of how he defeated one of his training instructors in Risk to Lister and the Cat, obliviously ignoring the fact that both are verbally decrying his story as boring. Luckily for the latter two, Kryten suddenly appears in the room — literally. Blinking across different parts of the room several times, he explains he was investigating the science labs on Z Deck, where he found the plans and incomplete prototype for a matter transporter (or "matter paddle", as it gets dubbed) and then finished assembling it.
Excited at this, if only because it means an excuse to get away from Rimmer's Risk story, the crew all head down to Starbug and discuss what the point of such a device is. Kryten and Holly explain it has a functional range of 500 thousand lightyears, and its scanning system, which allows it to detect S3-class (read: life-supporting) planets, makes it an excellent exploring system. The crew decide to give it a go, but Kryten suggests that he and Rimmer should be sent on ahead as a scouting party first; as a mechanoid and a hologram, they would be unaffected by atmospheric difficulties (non-oxygen atmosphere, temperatures fatal to organic life, etc).
Rimmer protests - not due to his congenital cowardice, as Kryten has already anticipated, but because as a hologram he can't interact with the matter paddle. Kryten and Holly then explain that Rimmer does have a small physical presence as a soft-light hologram; a floating projection unit, called a light-bee, hovers around inside of a hologram to project the image. Holly switches the projection off and Kryten can easily grab the light-bee, showing it to Lister and the Cat. Lister can't resist tossing the light-bee into his mouth and then spitting it out, but Kryten rescues Rimmer before Lister can seriously consider playing squash with it. Explaining that the paddle will be sent back if the planet is human-friendly with programming to bring the second party to the same planet at a slightly different point, Kryten and Rimmer vanish.
They rematerialise upon a lush world, and then send the paddle back after ascertaining it's safe. However, it turns out that they may have been a bit premature when two huge monsters suddenly appear, prompting both artificial sentients to run for their lives.
Unaware of what has befallen their comrades, Lister and Cat promptly teleport to the same planet, and find themselves in the war room of no less than Adolf Hitler, Goebbels and Goering! Lister and the Cat try to use the paddle to escape and believe they have done when they finally materialise in a narrow vertical stone passageway... which turns out to be the chimney of the war room, leading to them being captured and sent to prison.
Meanwhile, Kryten and Rimmer are commenting on how bizarre and improbable the creatures they fled from were; Kryten insists he's seen more realistic dinosaurs given away free in boxes of breakfast cereal. Then, to their surprise, they find themselves being taken captive by Elvis Presley and Pope Gregory!
In prison, Lister and Cat talk about what the Nazis have planned for them, while Lister starts looking out the cell window. As he does, he realises that their captors aren't Nazis - at least, not entirely. He notes that he can see all sorts of historical villains; Al Capone, Benito Mussolini, Richard III, Napoléon Bonaparte, even Rimmer's favorite musician James Last. It's as if all of history's worst people have been gathered into a single place. Then, to his horror, he watches as Winnie-the-Pooh is led out, tied to a stake and shot by a firing squad. Then the door to their cell opens and Abraham Lincoln is thrown in with them. He then begins to explain this weird world to them...
Back with Kryten and Rimmer, they find themselves brought into an armed bunker and presented with several famous figures; Pythagoras, Albert Einstein, Stan Laurel, Noël Coward, Marilyn Monroe... They promptly ask who Kryten and Rimmer could be, recognizing that they aren't waxdroids like they are. It's explained that this planet is an abandoned waxdroid-populated themepark, the residents of which slowly broke their programming over eons of neglect and have achieved full sentience. However, the villainous character waxdroids launched war on their more peaceful counterparts, and have almost conquered the planet; all of the heroic war-leaders like John Wayne, Sir Lancelot, Horatio Nelson, The Duke of Wellington, Joan of Arc and Doris Day have already been wiped out. Elated by this discovery, Rimmer immediately sets out to take charge of the survivors as their new general, discovering his remaining subordinates also include Jean-Paul Sartre, Santa Claus, Saint Francis of Assisi, Mahatma Gandhi, Mother Teresa, the Dalai Lama and Queen Victoria.
Meanwhile, Honest Abe finishes explaining the situation to Lister and the Cat, concluding that the villain waxdroids' intention is to melt down all the heroes so they can use their wax to create more villainous waxdroids. At that moment, Caligula and Rasputin enter to interrogate the two Dwarfers on how to use the matter paddle. The two manages to trick the two waxdroids into teleporting into a nearby cupboard, then escape with Lincoln, who leads them to the heroic waxdroid bunker. Unfortunately, Elvis takes them prisoner and presents them to Rimmer.
Rimmer is growing increasingly mad with power, and doesn't react well to Lister's criticisms of his efforts at being a general. Finally, he orders Lister and Cat imprisoned and then goes off to lead his grand assault.
The bulk of Rimmer's forces are sent charging across a minefield in full view of the villain command in the middle of the day, resulting in them being wiped out to a droid. Whilst this is going on, Kryten and Queen Victoria are sent to infiltrate the command bunker; the Queen shoots Hitler and his immediate subordinates, but is gunned down by the dying Fuhrer, leaving Kryten to seek out the boiler room and set the planet's temperature to 100 degrees, which causes all of the waxdroids on the planet to melt into lifeless puddles.
Retrieving the matter paddle, Rimmer and Kryten return to release Lister and the Cat, with Lister being highly disgusted with Rimmer — especially because Rimmer sees no problem at all with what he's done. Finally, Lister commands that Holly deactivate Rimmer's light-bee, which he swallows before he, Kryten and the Cat return to Red Dwarf.
- Alternate Character Interpretation: In-Universe — Kryten advocates the theory that Rimmer's particularly deranged behavior may be due to Lister's chewing on his light-bee.
- Apocalypse How: Rimmer's plan wipes out all waxdroids on the planet; those not killed in battle melt when the heating is raised too high. Tellingly, Rimmer considers this a victory for himself.
- Author Appeal: This may have been part of the reason that Queen Victoria took part in the attack on the Villain World headquarters, cutting down a good number of their Evil Wax-Droids. The show IS British, after all.
- Blood from the Mouth: A variation. Since the waxdroids don't have any blood, they leak liquid wax out of their mouths, not unlike milk. Which is what the actors had to simulate the effect.
- Drill Sergeant Nasty / General Ripper / The Neidermeyer: Rimmer proves to be all three of these when placed in military control of Heroworld. Three of his troops melt from exhaustion under his training, then he gets them all slaughtered in what is blatantly a stupid military plan.
- Everyone Has Standards: Even Cat is disgusted by Rimmer's behaviour.
- Fantastic Racism: Rimmer angrily shouts Kryten down that his troops are "only waxdroids" when Kryten laments that Rimmer is pushing them to self-destruction. This may also be part of the reason he is so blithe about exterminating them.
- Firing Squad: Lister wishes he hadn't watched Winnie-the-Pooh refuse the blindfold.
- Grew Beyond Their Programming: The waxdroids started out as simple automatons repeating stock dialogue, but after millennia of isolation they've become independent (though they still resemble the people they're based on).
- Glory Hound: Rimmer's first suggestion after everything that's been said and done is to go out into the battlefield and bask in the glow of victory. This sets Lister off into swallowing his lightbee.
- Hollywood Tactics: A daylight charge over the minefield (The WHAT-field!?). While Rimmer is technically correct that it is the last thing the enemy would be expecting, that is because literally everyone knows that is a good way to get your soldiers killed rapidly. And Rimmer had less than 20 soldiers. Justified because A) he doesn't really care about his soldiers, B) he's the worst tactical mind on the planet with an ego about the same size of it, and C) it's a decoy charge, allowing Kryten to sneak by the defenses to find the boiler and hit the thermostat. Then again, Kryten's handle over the radio was Pawn Sacrifice. However, Rimmer still got all of his soldiers killed for the sake of victory.
- Hostile Animatronics: The crew find a planet built as a theme park, occupied by "wax droids" of historical figures. Over the millennia, the droids have broken their programming and are now engaged in a planetwide war between the good and evil characters. One side somehow ends up enlisting Rimmer as their new military leader in order to break the stalemate. He... technically succeeds.
- I Will Punish Your Friend for Your Failure: Lister and the Cat are captured by Caligula and Rasputin. Caligula's response to everything the Cat says is to slap Lister.
- Nice Job Breaking It, Hero!: The reason Rimmer's even more deranged than usual, leading to the deaths of every droid on the planet, is Lister prankishly chewed and swallowed Rimmer's light bee at the beginning of the episode.
- Noodle Implements: Perhaps its best we don't find out what sort of torture Caligula had planned for Lister involving a bucket of soapy frogs, a diving suit with the bottoms cut out, and a rampant wildebeest.
- Pyrrhic Victory: Though all the villains are killed, Rimmer's waxdroids are wiped out from his commands. If any survived, they were killed when Rimmer has Kryten turn up the temperature, melting all the waxdroids. Rimmer considers this a victory. Lister lampshades how stupid this is.Rimmer: I brought about peace. Peace, freedom, and democracy!Lister: Yeah, Rimmer, right, absolutely. Now all those corpses out there littering that battlefield can rest easy, knowing they snuffed it under a flag of peace and can now happily decompose in a land of freedom... you smeghead.
- Stylistic Suck: The prehistoric beasts are Stock Footage from an obscure Kaiju movie, Daikyojū Gappa, and the film was even played with scratches and such to make it more unconvincing.
- Variations on a Theme Song: The closing theme is sung by Elvis.
- When All You Have Is a Hammer...: Pythagoras is utterly obsessed with triangles and believes they are the solution to the Wax War.