Batman and the world’s greatest escape artist, Mister Miracle, are performing a tandem escape for charity while manacled to a rocket-powered train on a roller coaster. As they avoid the various death traps along the track, they discuss Mister Miracle’s marriage to Big Barda. The rockets kick in, slamming the train toward a wall of spikes. The heroes get free just in time and float down to earth. As the audience applauds, Big Barda notes that the real miracle would be if her husband would clean out the garage.
In the distant future on a devastated Earth, an army of gorilla-men battle the opposing tiger-men. Both sides use human slaves for transportation. Kamandi, the last boy on Earth, and his ally Dr. Canus watch and figure they can help the slaves escape while the two armies battle. However, among the tiger-men are Prince Tuftan, son of King Caesar and a friend of Kamandi’s. When Tuftan is endangered, Kamandi comes to his aid. Caesar watches as his son leaves with Kamandi. The tiger-men defeat the gorilla-men, who make a hasty retreat despite the orders of their king, Ramjam.
That night, the gorilla-men regroup and Ramjam berates them as cowards. A figure steps from the shadows and says that Ramjam is the one who failed. The newcomer pulls back his hood to reveal… Gorilla Grodd.
In the present, Batman trails Gorilla Grodd to the laboratory of Professor Nichols. Nichols explains that the supervillain used the equipment to travel into the future. Nichols gives Batman a retrieval device that will let the time ray bring him back home, and then sends him after Grodd.
Grodd drives back the gorilla-men using his advanced technology, technology unknown in the future. Ramjam is impressed and challenges Grodd to single combat to determine who will lead the gorilla-men. Grodd defeats Ramjam and takes command of the army.
Kamandi, Tuftan, and Dr. Canus attack a squad of tiger-men gathering slaves. The humans, passive after years of enslavement, don’t run when freed. The freedom fighters are soon overwhelmed until Batman arrives to even the odds. However, the tiger-men capture Tuftan and Canus and force Kamandi and Batman to surrender. Back at the tigers’ city, Caesar visits the captives and tells his son he will work in the dungeons until he learns the error of his ways. For the others, the sentence is death. Batman tries to warn Caesar about Grodd, but the tiger-man doesn’t believe he has anything to fear from any gorilla. However, Grodd leads his army on the city and uses a sonic cannon to disrupt the tiger-men’s hearing, causing extreme pain. He then sends a giant gorilla, Tiny, to break down the gates. The gorilla-men storm the city and easily defeat their rivals.
Batman uses an acid capsule from his utility belt to break open the cell. The four prisoners flee into the city. They spot Grodd, who smells Batman and realizes that the Caped Crusader has followed him to the future. With Tuftan’s help, the fugitives evade the gorilla-men and escape into the sewers. Batman has a plan and sends Tuftan off on his own while he takes Kamandi and Dr. Canus to a special place: the old Batcave. The equipment there still works but bat-men now occupy the cave. They attack, thinking Batman is trying to mock them. The heroes defeat them and the bat-men are forced to flee. Batman then starts repairing one of his vehicles.
Grodd and his army are marching through a cannon and discover new opposition: the various other animal-men armies, organized by Tuftan. He fires the sonic cannon again but Batman, Kamandi, and Dr. Canus arrive in the Batplane and destroy it with missiles. Tuftan leads the armies and Batman ejects himself and the others, and then smashes the Batplane into the wall of cannon. The gorilla-men are unable to retreat. As Batman descends, the bat-men arrive and offer to help, impressed by his bat-like abilities.
Upon landing, Batman goes after Grodd while Kamandi and Tuftan fight Tiny. The two friends manage to trip the giant ape, leaving him easy prey for the animal-men armies. Batman takes on Grodd, preventing him from rallying his troops. The gorilla-men panic, stampeding over Grodd as he tries too late to stop them.
Later, Batman takes Grodd into custody while Caesar admits that he misjudged the humans… and his son. He orders the human slaves freed. Batman activates the time retrieval device, and suggests that the next time he and Kamandi meet it might be in Batman’s time.