(NOTE: The following recap is based on the English dub of the 1994 animated film.)
The story begins with Francis, a highly intelligent cat, moving into a new neighbourhood in Germany with his good-natured but not-very-bright human owner, Gustav Löbel (“Gus”, for short). Francis despises moving, especially as the house they've come to is particularly tumble-down, but Gus, who originally studied as an archaeologist, now makes money by writing pulp romances for magazines, and moving house is his way of solving writer's block.
While exploring the house, Francis notes an awful chemical smell coming from the top floor. He soon discovers something far more horrific - the dead body of another cat in the back garden, throat torn open. At the same time, he meets Bluebeard (Blaubart in the German original), a surly and foul-mouthed Maine Coon with a missing eye and tail and a mangled paw. Bluebeard, convinced that a “can-opener” (cat slang for human) is responsible, reveals that the dead cat - Sascha - is, in fact, the fourth killed in the last month. Francis inspects the body and dispells Bluebeard's theory by pointing out that the wound is a bite mark, not a clean cut.
That evening, while Gus entertains his friend Archie, Francis finds evidence that a plaque had been removed from the front of the house, and concludes that his new residence might have been a doctor’s office, which would explain the chemical smell. He goes to bed, and has a nightmare of following a light upstairs into a white room, where a faceless man gives him a diamond-studded collar. The collar morphs into an iron manacle around his neck, and the man drags Francis on a chain through the collapsing floorboards and into a hellish, fiery vortex.
When Francis awakens that morning, he is visited by Bluebeard, who informs him of another murder victim - the elderly Deep Purple. Francis has already figured out that all the murdered cats are toms, and asks to see Deep Purple’s corpse. On the way, they are confronted by the local bullies; the giant Himalayan cat Kong and his minions, the Oriental Shorthairs Hermann and Hermann. Bluebeard gets the bigger cat to back down, but Kong warns Francis that he’ll be looking to meet him again soon.
Upon reaching Deep Purple’s body, Francis discovers that the old cat was in heat before he was killed, despite being supposedly too old to be interested in sex. Sexuality, in fact, seems to be the link between the cases, as Sascha was also in heat before his death. Francis needs to get to know the neighbourhood for help in cracking the case, so Bluebeard offers to take Francis to meet another ‘genius’ cat the next morning.
That night, Francis is awoken by a racket coming from upstairs. Following the sounds, he is horrified to find cats leaping into an exposed electrical current, the machine operated by a cat who preaches on the subject of “Claudandus”. Furthermore, cats that Francis recognises - Kong, the two Hermanns and Bluebeard - are present at the gathering. Francis, however, gives himself away, and the cult members chase him into the attic, where he discovers remnants of what appears to be a laboratory. The chase continues across the rooftops, and Francis escapes by falling through a skylight into another house.
It is in this house that Francis meets Felicity (Felicitas), a blind Russian Blue. Felicity proves a key earwitness, as she heard the death cries of the victims - but she also heard a voice prior to the murders, of somebody trying to convince the victims of something. She also confesses to having pictures in her head of humans tormenting her, which Francis believes to be memories linked to the cause of her blindness. Bluebeard arrives, and Francis leaves, promising to meet Felicity again.
The next morning, at breakfast, Francis chastises Bluebeard for not telling him about the cult earlier. Bluebeard explains that the “Claudandus Sect” has been going for quite a long time, with the preacher cat - Joker - operating as its high priest. He insists the cult is nothing more than cheap thrills, especially as nobody knows who Claudandus was or if he really existed, but Francis isn’t convinced. After breakfast, Bluebeard takes Francis to meet Pascal, an elderly Havana Brown whose owner is a parapsychologist named Dr. Ziebold. Pascal has been using his owner’s computer to keep a record of the cats in the neighborhood, with the hope that it will help solve the murders.
Francis is able to use this database to confirm a suspicion he has - that all five victims, aside from being male and in heat, were European Shorthairs. Pascal suddenly reveals, however, that there has just been a sixth victim. Francis watches as Pascal types the name in…
A horrified Francis runs back to Felicity's home, but is too late. Felicity has been decapitated completely, lying in her own blood, her blind eyes staring up at the skylight. Francis is badly shaken and swears to avenge Felicity's death, but suspects that Felicity was killed because she was a witness, which means that it is very likely that the murderer is watching Francis’ every move.
Francis is wracked by another nightmare that night. In it, a gigantic Gregor Johann Mendel emerges from a sea of mangled cat corpses and repeats Pascal’s words on the subject of felidae to Francis. He then proceeds to puppet the corpses like marionettes, making them jump and dance around, all while laughing hysterically:
Upon waking, Francis goes rat-hunting in the basement to clear his mind. During this hunt, he crashes into a VHS linked to a TV set, which turns on and plays a video diary. Francis, curious, watches, and learns that the house was a laboratory, run by Professor Julius Preterius and his assistants Ziebold and Gray. Funded by the Pharmarox corporation, Preterius was trying to pioneer a revolutionary new tissue-bonding adhesive, using cats as his test subjects. The experiments were repeated failures, as the substance instead acted like acid, eating its way through the cats skulls into their brains, killing them. In desperation, Preterius used a stray cat the lab had adopted as its mascot as a test subject - and found, to his surprise and delight, that the mixture worked. The cat was thereafter named “Claudandus”, a Latin word meaning “to be closed”.
But the glue only worked for Claudandus - he was a mutant who could absorb the mixture without side effects. Refusing to give up, Preterius performed further experiments on Claudandus, descending into alcoholic insanity as he continued the project long after Pharmarox cut off his funding and his assistants left him in disgust. In order to keep up his supply of test subjects, Preterius began breeding his animals, which gave him flights of insane fancy about a "super race" of cats. The tape ends with a now-crazed Preterius claiming that Claudandus had spoken to him…
Unfortunately, Kong arrives to resume the earlier confrontation, with the two Hermanns backing him up. The Himalayan boasts that he is the killer, who took out the others for not showing him proper respect. Francis doesn’t buy this motive - Kong is a brute, no doubt, but he hardly seems like a murderer. Even so, a fight starts, which Francis barely escapes from. Fleeing across the gardens of the neighbourhood, Francis makes another gruesome discovery… a female cat, murdered in the same way, but with her belly ripped open and unborn kittens spilling out.
Kong recognises the body as Solitare, his mate, and is driven to grief and anger by her murder. When a strange cat runs across the garden, Kong assumes them to be the killer and gives chase in his rage, but loses him. Francis sees the strange cat entering a tunnel and follows, eventually joined by Bluebeard. Together, they find an underground chamber filled with cat skeletons and corpses - but not, as Bluebeard notes, the bodies of previous victims Sascha, Deep Purple or Felicity.
They also meet the strange cat - an elderly and eccentric Persian named Isaiah (Jesaja). Isaiah protests his innocence, claiming that the bodies are sent by the “Prophet” for him to watch over.
Francis questions Isaiah, who tells an odd tale of a “suffering dreamland” where he was born. The Prophet - Claudandus - came among them and took the suffering of the others onto himself, and eventually prayed to God for salvation, destroying the dreamland and freeing the other cats but dying himself. This latter fact was told to Isaiah by Joker, who took Isaiah in and nursed him to health, but left to spread the gospel of Claudandus. When the first dead cat came to Isaiah, he heard the voice of the Prophet, commanding him to be the Guardian of the Dead and watch over the bodies that came to him. Isaiah admits that many cats that came to him were in heat or strangely mutilated, and that many of the females were pregnant - a fact that distresses him. But no bodies have come for a while now, which was why Isaiah had emerged - he was trying to carry on what he thinks of as his God-given task.
Francis realizes that the murders go much further back than he suspects - as far as the closure of Preterius' lab - and that the only cat who has any idea of whom Claudandus really was is Joker, making him the prime suspect. When he gets home, he takes a nap, deliberately invoking a dream to try and sort the clues out in his head. In his latest dream, he is faced with a gold-furred, blue-eyed cat who calls himself Felidae. Felidae implores Francis to join him and many other cats he recognises on a “long and wonderful journey”.
The call of a female in heat wakens Francis from his dream, and he follows it outside to investigate. The female in question is of a breed he doesn’t recognise, with sandy fur and blazing yellow eyes. After they mate, Francis questions her, but her answers are cryptic and obtuse - she only states that her breed is both “new and old”. They mate all day, leaving Francis sore and exhausted, much to the amusement of Bluebeard when he pays Francis a visit later. Bluebeard reveals that many cats like her are appearing around the neighbourhood, being taken up as designer pets, but this breed is far from domestic. They’re wild, independent and, in Bluebeard's opinion, dangerous.
Francis goes to visit Pascal while Bluebeard searches for Joker. Together, Pascal and Francis piece together the idea that the killer, rather than simply getting sloppy, is trying to leave a message to somebody about his work. They also float various theories about the mysterious female that Francis mated with, which Pascal somehow knows about. Bluebeard’s search is unsuccessful, only getting a bad fright when he finds a room full of cat statues, and he comes back to tell Francis and Pascal that Joker has seemingly vanished. Pascal floats the idea that Joker has run away to avoid being questioned, but Francis can't accept that. Pascal therefore offers to use his database to look up cats who might have been in Preterius' lab before it closed.
On the way home, Bluebeard warns Francis that the killer might try to go after Francis to avoid justice. Francis worries that Pascal might also be a target since he knows so much, but Bluebeard reveals that Pascal is castrated, meaning he’s not somebody the killer, who has only focused so far on sexually active males, is likely to target. He also drops a bombshell - Pascal has cancer (colon caner in the German original, stomach cancer in the English dub) and only has half a year to live.
A conference is held at Francis' home, where Francis and Pascal reveal that the murderer has over four hundred deaths on their hands, and that the killings go as far back as the experiments at Preterius’ lab - to which many older cats in the neighbourhood, Bluebeard included, were subjected to. A kitten suddenly interrupts, saying that her grandfather - Joker - told her that Claudandus didn’t die, but fought with “the monster” Preterius and killed him. Pascal rebuffs this, claiming that nobody could have survived those experiments. He offers an alternative explanation - Joker is the killer, who took the name of the prophet for his own and fled when he sensed Francis was catching up to him. The neighborhood cheers, considering the case solved, but Francis isn't convinced and begins to suspect Pascal.
Francis and Bluebeard go back to Joker's house to take another search. Climbing a tree, Francis peers through the skylight and finds Joker dead on the top shelves among the cat statues. But there's no sign of a struggle, and the peaceful attitude of Joker's body shows that he allowed himself to be killed, implying that he died to protect some big secret. Francis deduces that secret could be that Claudandus is still alive.
At Francis' home, the duo ponder the mystery further. A glance into one of Gus' Egyptology books gives Francis a flash of inspiration, and he fetches a G-word dictionary from Gus' shelf. Finding the page on genetics, Francis reads a passage on Gregor Mendel and comes to a shocking conclusion:
Francis begins to put the clues together at last. The faceless man from his first nightmare was Preterius, whose experiments kickstarted the entire horror. Felicity overheard the killer talking to his would-be victims; far from being a psychopath, he was trying to persuade Sascha, Deep Purple and the rest to not mate with the mysterious females. Said females are modelled on the Egyptian ancestor of cats, containing the desirable traits that would return cats to their original wild, dangerous form. Thinking about the Mendel nightmare, Francis recalls seeing a portrait of Mendel in Ziebold's house - the same Ziebold who worked with Professor Preterius. Francis and Bluebeard head to Ziebold's to finally solve the mystery.
The two cats split up, with Francis searching Ziebold's computer for evidence while Bluebeard searches for Pascal. Bluebeard is attacked from behind and knocked unconscious, while Francis finds a hidden file and guesses the password - Preterius - to access it. What he finds isn't a database on neighbourhood cats, but a breeding record that also lists the murder victims. Francis finally understands the killer's true mission: to ensure that only racially-suitable males mated with the females chosen to re-establish felidae. Any undesirable male that wouldn't listen to reason...
Pascal is, indeed, Claudandus. When Preterius went mad, Claudandus convinced him - by speaking to him - to open his cage, then killed him before setting the other cats free. Ziebold would take him in, and through Ziebold, Claudandus would educate himself on Mendel's theory of genetics, which gave him the idea to breed back felidae and create a new species that could someday overthrow man. Joker, Claudandus' sole ally, used the cult to disseminate the philosophy of the project while Claudandus handled the breeding program. As it expanded, Claudandus was forced to kill in order to keep the bloodlines of his new felidae pure, with the bodies handed to Isaiah to keep them hidden. He also admits to killing Joker, who agreed to die to avoid spilling the whole plan to Francis under pressure.
Knowing that his cancer was terminal and that he only had a short time left, Claudandus put Francis, whom he saw as an equal and like-minded individual, on the track of the murders. It was his hope that Francis, once he understood the mission, would agree to become his successor and carry on his work once he has passed on. Francis, however, is disgusted by what he hears. He accuses Claudandus of being no different to the humans who tormented him, wanting only to inflict the same torment upon mankind that he'd been subjected to.
Resolving to fight Claudandus' insane scheme, Francis tries to delete the database on the felidae breeding program. Claudandus attacks, knocking over the computer, and a fire breaks out as the two cats fight fiercely. As the flames roar higher, Francis triumphs by ripping open Claudandus from chest to groin, fatally disembowelling him. Lying amongst his own entrails, Claudandus speaks for the last time.
And with that, Claudandus dies. Francis flees the burning building, finding the unconscious Bluebeard and dragging him to safety. As the fire rages on, Francis collapses in the snow.
Following the murders, things appeared to have settled back to normal. As Francis meets up with a felidae female, the species having integrated itself into the neighborhood, Francis speaks to the viewer, imploring them to never stop believing in a world where humans and animals can coexist in peace, even if it will take a long time and much work to get there.
