Caiman, a large man with a spiked lizard-like head and red crosses tattooed on his eyes, pushes the head of a sorcerer, Matsumura, into his mouth; a man slides up Caiman's throat, also with red crosses tattooed on his eyelids, and tells Matsumura "You're not the one." Matsumura's partner, Fujita, escapes the grasp of Caiman's friend Nikaido to try and save him, only to find Caiman is unaffected by his magic before Nikaido breaks his finger. Hearing what the man in his throat said from Matsumura, Caiman instantly slices him into multiple pieces. The dying Matsumura's severed hand summons a door under Fujita, allowing him to escape. Caiman and Nikaido head back home, with Caiman stopping to look down the alleyway where he was found; two years previously Caiman was found unconscious in the alley by Nikaido, his memory blank and his head reptillian. Since he can dispel the sorcerer's magic by killing the caster Caiman has been shoving sorcerers heads into his mouth since, hoping that the man inside his mouth will identify the culprit.

Spending most days working at a hospital for magic victims or eating at Nikaido's restaurant, The Hungry Bug, Caiman returns one day to find a rookie sorcerer transforming Nikaido into an insect. Caiman quickly kills the sorcerer, which turns Nikaido back to normal. The next day, Nikaido and Caiman take a picture of the inside of Caiman's mouth, unsuccessfully trying to get a clue to the head's identity. Spotting a female sorcerer, Ebisu, emerging from a magic door, Caiman grabs her and shoves her into his mouth. Fujita suddenly emerges through another door and grabs Ebisu, pulling her from Caiman's jaws and back to the sorcerers' world, accidentally tearing her face off in the process. That night, Caiman has a nightmare about the person inside his mouth. Elsewhere, a pair of sorcerer cleaners named Shin and Noi murder a group of gangsters with red crosses tattooed on their eyelids.

Shin and Noi are called in for a meeting with their boss, a highly reputable sorcerer named En. En also summons Fujita and Ebisu, and asks Noi to heal Ebisu's face to find out what she knows; while Ebisu's physical wounds are easily healed, the mental distress has placed her in a dissociative fugue, leaving her with no memory and reduced mental and magical skills. En requests the group find and kill Caiman and Nikaido. The group is suddenly attacked by assassins, whom En easily dispatches by turning them into mushrooms with his magic.

Caiman's boss, Vaux, tells him to toss a trash bag in the incinerator, inside which Caiman finds a dismembered person who cannot die. The "murdered" man was disassembled and tortured with Shin's magic before being thrown into Hole, with Shin's magic preventing his separated pieces from dying. Caiman tosses him in the incinerator to end his suffering. Later, Caiman and Nikaido head to another town in Hole to visit a magical Acupuncturist who might be able to give Caiman his human face back. Nikaido fights off some attackers while out shopping and gains a clue to the Acupuncturist's location. The two then head to a bar where the Acupuncturist tries to change Caiman's face, but all Caiman does is shed his skin with no visible change.

Several Hole residents arm themselves for the "Night of the Living Dead." Once per year the severe magic pollution in Hole causes dead people to rise from the grave as zombies, forcing local priests to bury dead with metal tokens that can be exchanged for prizes. Caiman, Nikaido, and Vaux decide to join the festivities, with Nikaido hoping to buy a new meat grinder with tokens. Shin and Noi head to Hole with Fujita and Ebisu, hoping to find and kill Caiman and Nikaido but finding themselves in the middle of the zombie invasion. Ebisu is soon bitten by a zombie, turning her feral.

Shin and Noi soon find and seriously injure Nikaido and decapitate Caiman. Nikaido uses magic power to create a door and escape with Caiman's body and head, revealing she is a sorcerer. Five days later, Caiman recovers in the hospital by inexplicably regrowing his head. Vaux tells Caiman that Nikaido is a sorcerer, but Caiman doesn't believe him. Caiman returns to the Hungry Bug as Nikaido wonders what he'll think of her past as a sorcerer. Soon after Vaux appears with Caiman's severed head in a jar, suggesting they record a dissection of the head. Early into the dissection the hospital's power suddenly cuts, and the head disappears in the confusion, the only evidence a shadow briefly captured on the camera.

The En Family visits a sorcerer named Turkey, who uses magic to bake temporary clones that can lead people to a target; En hopes it will lead them to the sorcerer who cast magic on Caiman. Turkey's clone leads the En Family to an abandoned apartment, where they discover a rotting head in a safe. After fighting the angered clone for it, Noi heals the head and discovers it's the same as the clone's, a member of the anti-magic Cross-Eyes gang that opposes En. Later, the En Family goes to a formal party at a mansion where En hopes to recruit a potential partner: a sorcerer with the ability to bring people back from the dead. Shin and Noi kill a couple of sorcerers who are using illegal black powder to enhance their powers, and En discovers the true form of his new partner: a small cat-like creature hiding under the supposed necromancer's dress. En kills the false necromancer, adopting the creature and dubbing it Kikurage.

Meanwhile, in Hole, Caiman and Nikaido go to visit Vaux's colleague, another doctor, who might be able to help Caiman find his identity. After entering the doctor's home, the duo find it to be a labyrinth they can't navigate, and decide to have an impromptu New Year's Day meal. In the middle of the meal they are joined by Kasukabe, the doctor in question, who explains magic dust has started to gather in his house, affecting the architecture. After vacuuming the dust and restoring his house, Kasukabe then shows the duo a magic door, made from vivisected sorcerers, that allows passage to their world.

Disguised as sorcerers, Caiman and Nikaido begin searching for clues. Pausing to eat at a restaurant, Nikaido wanders off and is handed a calling card by a demon, while Caiman suddenly recovers some of his memories, realizing the man in his mouth was a person he knew called Risu. Concurrently, En uses Kikurage to revive the Cross-Eyes head found in the safe, who reveals he is Risu. En places Risu's head on a magic-powered mechanical body and interrogates him further, but Risu provides little information of value.

En sends Shin and Noi to follow a lead on a base owned by Cross-Eyes. Initially trying to negotiate with the Cross-Eyes for their boss' location, Shin and Noi are attacked but easily retaliate and kill them. Caiman and Nikaido stalk a Cross-Eyes member they spot in the restaurant, only to lose and then find him after Shin and Noi's massacre. Their leads cold besides Risu's name, Nikaido suggests she and Caiman split up to cover more ground.

Working alone, Nikaido sells her powder in a magic smoke pawn shop, killing the owner and stealing back her magic once he pays her. Nikaido then meets with a devil named Asu, who reveals that Risu is being held by En; she breaks into En's mansion only to encounter Noi, who challenges her to a fight.

Nikaido evades Noi, finding her way to Risu. Trying to abduct him, Nikaido punches En and shatters his mask, enraging him and causing a huge magic outburst that covers everything in mushrooms. Risu, unaffected by En's magic due to it powering his prosthetic body, uses the confusion to flee. Nikaido also narrowly escapes but is injured, forcing Caiman to take her to Vaux when a huge mushroom sprouts from within her back. Speaking with Vaux and Kasukabe, Caiman learns that they know Shin as their former patient.

A flashback shows that sorcerers were historically considered outlaws in Hole, hunted and killed by human gangs. Shin, unaware his late mother was a sorcerer, accidentally bleeds magic dust at work, causing his boss to inform the local vigilantes. Fleeing, Shin returns home to find his father has been tortured to death by the vigilantes, prompting him to single-handedly murder them with a claw hammer. Shin uses hospital equipment to vivisect his arms and try surface his magic veins, hoping to increase their power at risk of bleeding to death; he is found by Drs. Vaux and Kasukabe, who reconstruct his arms and surface his veins, fully activating Shin's magic but leaving his arms paralyzed. Following Shin's surgery, Vaux and Kasukabe receive a large influx of magic victims: the remaining local vigilantes, whom Shin has dismantled into living pieces using his newly acquired magic, leading to the dissolution of Hole's vigilantes.

In the present, Kasukabe insists to Caiman that Nikaido is a sorcerer, noting that they operated on her and that sorcerers have distinct anatomy due to their magic veins. Hearing a scream, Caiman runs to her room and finds she's been abducted from her bed. Pursuing the kidnapper, Kaiman follows them into the sewers at the alley where he first awoke. The kidnapper mistakenly believes that crystallized beads of magic powder in sorcerers are gemstones that can turn him into a sorcerer. Pinned by the kidnapper's giant cockroach, Johnson, Caiman attacks the kidnapper, cutting off his feet and throwing one of them out to distract Johnson. The kidnapper claims to recognize Caiman and Nikaido from the day the former appeared, only to die from blood loss.

En buys the magic pawn shop and has Shin and Noi investigate it, discovering that Ebisu has sold her magic powder there several times; he orders her stocked powder to be examined to learn her magical specialization. Despite his help, En reveals he has been unable to find Fujita a replacement partner. A bitter Fujita heads to Hole, plotting to find and kill Caiman with a pistol; while initially taunting his unpopularity, Ebisu follows him to help. Shortly afterwards, a worker returning with Ebisu's magic powder trips, accidentally throwing the vial and smashing it on Noi, causing her to scream.

Vaux, visiting The Hungry Bug, bemoans that they lack a required ninth needed player for their baseball match against a rival hospital; Thirteen, a regular at Nikaido's restaurant, volunteers himself. Across Hole, Fujita applies at the rival hospital for their pitcher position to get closer to Caiman, with Ebisu being taken as their mascot. Preparing to pitch, Fujita is horrified to see their first batsman is Matsumura, his corpse reanimated by Kasukabe (à la Frankenstein's monster) and kept docile using electricity. The rival hospital begins cheating to try and win the match, with Ebisu drugging their remaining pitchers; in response Kasukabe uses Johnson, domesticated and controllable through elecro-shocking, to regain the lead. Fujita then begins sipping a drink that increases his smoke output, allowing him to affect the speed of the ball; Nikaido, skilled enough to bat the shot, accidentally concusses the rival hospital director, allowing Fujita to escape with Matsumura during the confusion.

Shin follows Noi, who has turned into a reptilian humanoid due to Ebisu's magic and began an uncontrollable rampage. Shin narrowly manages to incapacitate Noi, getting seriously maimed in the process. En has Shin carry Noi up to a man called Chota, a sorcerer obsessively infatuated with En, who restores Noi to normal by mixing a dispelling potion. Elsewhere in the mansion, Ebisu complains her head hurts from stealing Fujita's smoke-enhancing drink, only to be attacked by the undead Matsumura, who has become violent without his shock treatment. Overwhelmed and under attack, Ebisu emits a huge amount of magic and transforms herself into a huge dinosaur, causing her to crush Matsumura's remains into a paste in a rage.

Fujita takes Matsumura's pulped remains to Kikurage, who is unable to restore him to life. The report on Ebisu's magic powder explains she is the sorcerer who can turn things into reptiles; Ebisu confirms this, her returning memories including the man in Caiman's mouth saying "You're the one who got in my way!" Caiman, unwilling to let Nikaido get hurt any further, quits his job and heads back to the sorcerer world alone, leaving Nikaido to learn of it from Vaux. Shortly after arriving in the magic realm Caiman intervenes in thugs trying to kidnap a pie-maker named Fukuyama, leading Fukuyama's bosses Tanba and Kirion to take him in as cover staff for his pie shop.

Risu returns to his apartment, where his head was found inside a safe, and recalls his death. Sent on a routine job by the Cross-Eyes, he turns down his friend Aikawa's offer for company as he is explicitly told to go alone. While he waits at his meeting point, an unknown assailant fatally stabs Risu from behind. Risu sees part of his killer's reflection as he dies, glimpsing a Cross-Eyes tattoo; he was murdered by a member of his own gang. In the present Risu realizes that he is starting to run out of magic charge, at which point his body will fail, and he'll be helpless.

En begins planning the Blue Night Festival, a multi-day event where sorcerers place ads and applications to seek a partner, ending the event by signing a demon's binding magical contract with their partners. Caiman sneaks into the event by leaving work and stealing an event employee uniform, but becomes sidetracked when other workers keep giving him responsibilities. Noi goes to the toilet alone only to be blown up by another magic user, Baku, who seeks to force her into being his partner over Shin.

Shin finds the bathroom destroyed and Noi missing, only to be incapacitated with sniper-fired sedatives by Baku's accomplice, Yaku. Caiman is accidentally injured by both Baku and Yaku, prompting Tanba to pick a fight with them. Caiman causes Baku to accidentally self-destruct by cutting off his cannon hand, while Fukuyama reveals his magic skill by turning Yaku into a giant meat pie, the group unknowingly saving Shin in the process. Elsewhere, Risu breaks into the Blue Night Festival to steal stored smoke, only to find Baku's magic-inhibiting chest containing Noi. He opens its door and unwittingly frees Noi. Her healing magic immediately triggers and floods the room, also regrowing Risu's original body in the process.

A flashback shows how Shin and Noi met a decade ago: a homeless Shin, his limp arms now rotting, is challenged to a fair fight for stealing food by En's cousin, revealed to be Noi. Shin's arms are healed and he strikes her with his claw hammer, fleeing while yelling he'll pay her back. Shin is shortly hired as En's cleaner and quickly becomes friends with Noi, who is undergoing grueling training to ascend into a demon; her final exam requires full magic abstinence for a year. As Blue Night approaches, Shin and Noi are attacked by Baku and Yaku, with Shin victorious, but fatally injured; Shin considers his debt repaid, but Noi immediately fails her exam to save his life. Hiring Noi as Shin's understudy, En pushes them into a contract partnership.

In the present, Noi finally locates Shin's unconscious body in time to renew their contracts before Blue Night ends. Fujita admits he's devastated that he couldn't find his only partnership applicant, only to realize it was Ebisu from her bashful response. En discovers Nikaido was also the pawn shop attacker and that her magic could be the rumored time control power he is seeking. En creates a voodoo doll of Nikaido, causing her to collapse at Vaux's birthday party as a huge mushroom familiar bursts from her mushroom scar.

Attacked by the familiar in The Hungry Bug, Nikaido and Johnson manage to distract it long enough for everyone to escape upstairs. In a flashback, Nikaido recalls receiving her sorcerer's mask from her demon friend Asu; climbing into her loft and recovering it, she gains the strength to easily defeat the familiar. This is revealed to be a trap, however, as the familiar's pooling blood turns into a door in the floor, dropping everyone into En's mansion. The head demon Chidaruma appears and confirms that Nikaido's magic can control time and, despite her blatant lack of consent, Nikaido is forced to exchange contracts with En. Shin and Noi also successfully renew their contracts, while an upset Fujita is unable to enter a partnership with Ebisu as she suffers diarrhea and cannot sign the contract before the night ends.

Caiman, suffering mysterious nightmares based on his unrecalled memories, goes for a late walk but is followed by Tanba, who interrogates him. Learning Caiman is actually a magic victim and not a sorcerer, Tanba offers to help him find the Cross-Eyes through a potential lead; he received a letter from a Cross-Eyes customer on death row who wants Fukuyama's pie as his last meal, and brings Caiman along. Caiman puts the prisoner into his mouth, who recognizes the man inside as Risu, but he cannot explain before he is dragged into Hell; Caiman is narrowly saved from the same fate when Asu appears, who warns him that Nikaido is imprisoned at En's mansion.

Nikaido's contract begins to make her submit to En, and En requests she be given a new mask by Chidaruma. Kasukabe, Johnson, Thirteen and Vaux escape En's dungeon, with Johnson having a cockroach pick locks and Kasukabe stealing Fujita's gun; Kasukabe holds him at gunpoint, only to be surprised and pinned by Shin.

Shin recognizes Kasukabe as the doctor who saved his life, and moves his group to a safe-house; later agreeing to release them, he refuses their appeals to free Nikaido too. In En's mansion Nikaido is mentored by Chota, who begins trying to murder her out of jealousy under the false pretense of assassination survival training. Chota then shows Nikaido an autobiographical movie that explains En's past.

En's substantial magic power turned his parents into mushrooms when he was a baby, leading him to be picked up by a burglar who sold him to a trafficking ring that bleeds sorcerers of their smoke for profit. Left to die once his smoke dried up, En's rage allowed him to survive even being thrown into Hell; eventually noticed by head demon Chidaruma, who named him En, he soon returned him to the magic world, where En began liberating sorcerers and building his family. After twenty years unopposed, En watched as his capos began dying to a sorcerer hunter, identified as a knife-fighter with cross tattoos on his eyes. With his inner circle dead and Shin and Noi seriously wounded, En attacked the assassin in a rage and blacked out; coming to with the entire neighborhood engulfed in giant mushrooms, later labeled a freak incident dubbed "The Death Shroom Incident", En saw the assassin step through a closing magic door despite being beheaded. The film ends, and En appears, explaining to Nikaido that he needs her time powers to return to the Death Shroom Incident and confirm whether the assassin really did survive.

Disguised as Tanba's pie mascot, Caiman assists him in a cook-off against his ex-wife Asuka held outside En's estate. Asuka tries to cheat the contest, enchanting her pies to make customers obsessed with them; Caiman seizes the distraction to drag Nikaido away from the distracted En. Nikaido stops Caiman and argues that she wants to be with En, unaware of the contract's effect on her. Caiman warns her that he's rescuing her by force if need be, and Nikaido asks if he thinks he can.

In a flashback, Risu reports on an implied assassination for the Cross-Eyes, only for his friend Aikawa to interfere and attack the gangsters. Aikawa warns Risu against affiliating with the Cross-Eyes, but Risu argues against it; despite attending a sorcerey school Risu is still unable to produce any magic smoke, and feels that the Cross-Eyes' rumored research in Berith is the only hope for people who can't use magic. In the present, Risu heads to Berith in search of his killer.

An unwilling Caiman is forced to defend himself against Nikaido, but refuses to seriously fight back; Nikaido beats Caiman severely, taunting him by confirming that she is a sorcerer. Hallucinating from a concussion and his legs crushed, Caiman tries to crawl to safety but blacks out; Nikaido pursues but is stabbed in the back by an unseen man she doesn't recognize. Chota gleefully finds Nikaido's body, only for Asu to appear and pull En's contract out through her wound; Asu hands Chota the contract in exchange for his silence. Nikaido wakes and Asu explains that she has only came to her senses temporarily: being close to En will cause her contract to regrow, with the only true solutions being En's death, Chidaruma nullifying it, or waiting for the next Blue Night to pass.

Caiman, unconscious from his wounds, recalls awaking in Vaux's hospital in a dream. Unable to remember even his name, Nikaido notes he looks like a caiman and suggests it as a nickname, which he adopts. Waking in the present, Caiman grabs Nikaido and shoves her in his mouth as she's a sorcerer; Nikaido informs him that the man in his mouth is Risu, and Asu informs them that Risu is currently in Berith. Asu opens a magic door to help them escape En, buying them time by transforming Chota into Nikaido's doppelgänger.

Exiting the door in a ruined city, Caiman and Nikaido hide from patroling demons in an abandoned subway. Asked about her past, Nikaido explains that her magic can control time, but she accidentally killed a friend with it, causing her to swear off using it for life. She began hiding in Hole to try and evade people like En who would want to exploit it, protecting humans from sorcerers in the hope she would become closer to a human. Given that she refuses to use magic and promises to stay friends when Caiman reverts to normal, they agree to stay friends.

As part of a sorcerer holiday, common magic users must make offerings to demons to receive their mask. Shin and Noi, notable sorcerers as part of En's inner circle, simply choose magic ingredients and are crafted a mask. Fujita, as a low-ranking sorcerer, must source a sufficient gift as an offering to receive a good mask; displeased with Fujita's gift, a transparent attempt at bribery, the demon punishes him, and he receives nothing.

Nikaidou, prior to owning The Hungry Bug, is a wandering street vendor struggling to make ends meet. Finding a tea shop named Syueron-Kan, empty save for one shady customer named Mr. Moroku, Nikaido enjoys tea poured by the owner Syueron. Thugs suddenly burst into the shop and attack Syueron, and Nikaido defends him; the thugs, disabled from magic experimentation, exclaim that Syueron's customers are sorcerers before leaving. Syueron admits that only magic users seem to like his tea, and that while his shop is busy at night with sorcerers he is regularly harassed during the day. Nikaido decides to work as Syueron's doorman, allowing him to comfortably run his shop for a few months while she saves up for her own business.

This suddenly ends when Nikaido comes to work to find the shop wrecked, and Syueron appears to explain it was destroyed overnight by the magic victim thugs. Syueron thanks Nikaido for everything, but says he's abandoning the shop; Mr. Moroku is actually a disguised demon, and has offered him a job at his estate. Wishing her well, Syueron and Mr. Moroku depart, leaving Nikaido pleased she has a shop, but bemoaning the repair work it will require.

Ebisu starts her daily routine, only to trip and fracture her skull on the stairs. Healed in Noi's room, Ebisu becomes fixated by the photographs on Noi's wall, disappointed she isn't in any of them. Told to visit En, Ebisu is disheartened when En explains she's not significant enough to be in any of his photos. Fujita approaches Ebisu, explaining that he convinced their photographer demon to take a picture with them in; while she receives her wish, Ebisu is displeased that she is only one of multiple people in the "underling" photograph.

The Gyoza Fairy, a small invisible sprite made of gyoza, presides over The Hungry Bug to ensure people properly enjoy their meals, such as cooling their beer and refilling their dipping sauce. While pleased that Caiman cares deeply for the dish he loathes that he eats it in excess and is unable to stop him. He then watches as Nikaido, out of pastry to make more for herself, watches in amazement as she uses the remaining filling to make a patty-based dish. The next day, the Gyoza Fairy notes that Nikaido is sick due to the rain, and witnesses Syueron and Mr. Moroku trying to visit only to find The Hungry Bug closed. Attempting to cheer up Nikaido, the Gyoza Fairy cleans the dirt out of her ventilation fan, only for a confused and displeased Nikaido to find her toothbrush returned covered in mold.

En is holding his decennial demon ball, where people are required to invite a partner to dance to give praise to demons, and invites all of his employees. Unbeknownst to new attendees the ball is incredibly tribal in nature, requiring participants to equip only grass skirts and spears and dance enthusiastically with partners under threat of being stabbed by demons.

Fujita, rejecting Ebisu as he feels he can do better, asks her to dance as apology; she refuses, fleeing and leaving him to be pursued by a demon. Shin recalls his first ball from shortly after En hired him, sadly unable to recall the unknown girl he danced with; offered a dance from Noi, he realizes too late that he danced with her before he knew her.

Shortly after first meeting Nikaido, Caiman finds shiso and ginger growing nearby, and takes them to The Hungry Bug. Nikaido decides to use the ingredients to make him gyoza, teaching him the entire recipe and process. Once done the duo eats on the restaurant roof, causing Caiman to exclaim in delight.