After having a dream of herself as a child, reading a picture book titled The Black Flame and The Golden Wind, being attacked by demonic creatures as a golden knight saves her, Kaoru Mitsuki prepares for her debut tomorrow as an artist. Meanwhile, a man named Kouga Saezima just finished his training when his butler Gonza gives him a document that directs him to the art gallery Kaoru is at. After seeing the girl not to be possessed, he follows the frighten girl to the art dealer Taisuke Taniyama, offering to play one of Kaoru's pieces early and asking for the girl to take it to his manor. Once alone, Kouga attempts to kill Taniyama who runs off and put the entire building on lockdown. After taking out Taniyama's traps, with Kaoru in the crossfire, Kouga battles Taniyama until the demon possessing him, a woman-eating Horror named Anglay, bursts out of his host and uses another painting to assume another physical form. Telling Kaoru to run, Kouga transforms into the golden knight from Kaoru's dreams. Though Garo manages to kill the Horror, some of its blood splashes on Kaoru's face and arm. Though he has to kill her for being stained with the blood of a Horror, Kouga spares her life to use her as bait for attracting Horrors. When she comes to, Kouga apologizes for ruining her big break before walking off with her painting.

After having another Horror-related dream, and attempting to dodge her landlord, Kaoru attempts to make some money as a melon bread salesgirl to make ends meet. But seeing Kouga, she runs after to get the money he owes her when she loses him. Entering the chamber of the Eastern Watchdogs to purify his blade, Kouga receives orders to get after the Horror Istarb who possesses the body of Azusa Kujo. Finding Kaoru waiting for him, Kouga gives her a ring as he promises to get her money soon. Meeting with her best friend Asami, Kaoru learns of the IT business proposal Kujo that was doing prior to becoming a Horror's vessel. Kujo instantly develops an interest in the girl as she is about to eat her when after scamming $50,000 yen from her. However, a combination of dumb luck and Garo stopping Kujo with Istarb slain. After learning of Kujo's scamming the next day, Kaoru is relived when Kouga brings back her money. From there, Kouga explains that the Horrors are demons from ancient times that target people with darkness in their hearts, telling Kaoru that hers is pure as he explains the ring given to her is a protective charm. As he leaves, Kaoru questions why Kouga has saved her life.

After finding the victim of a Horror, with the demon nowhere in sight, Kouga brings the dust remains to the Watchdogs who reveal it to be the work of Morax, a Horror that takes the form of timepieces which Kouga has never faced before. Working in a bicycle delivery service, Kaoru is tricked into finding the Saezima estate where Kouga wears her to stay away from any time piece for the day. By then, Kaoru learns of Kouga's Madogu Zaruba, who reveals the ring she wears as actually a part of him to the girl's disgust. Soon after, to further insure her safety, Kouga had Kaoru occupy the guest room with Gonza paying delivery fee as compensation. By nightfall, Kouga finds Morax as he devours a high school girl named Ayano, jump onto another girl to evade the Makai Knight through various hosts. However, taking a delivery for her shrink, Kaoru ends up being taken hostage by Morax as he assumes the form of an old clock tower. Fighting the Horror's defenses, Garo manages to rip out Morax from his vessel and kill him. With Morax dead the building fell apart and Kouga carries the unconscious Kaoru to safety before she comes to. Giving Kaoru back her watch, she attempts to demand answers when she realizes she is behind on deliveries.

Arriving to a hospital once noted of a Horror sighting, Zaruba cannot seem to detect anything out of the unusual. The next day, after being evicted, Kaoru forces her way into Asami's place, unintentionally getting her sick as she is taken to the hospital the same time Kouga attempts a second look over, uneasy about Zaruba inability to sense their surroundings. He then up with the wife of one of Dr. Tategami's patients, who she last saw going to see the doctor to thank him. Interested why a Horror would spare human lives to eat them, Kouga meets Tategami who reveals himself as a host to the Horror Pazuzu who explains he is preparing his meals for finer taste. Learning he cannot summon his Soul Metal Armor, Kouga is forced to fall back with Pazuzu summons his Horror staff to kill him. After refueling his Madoubi, Kouga decides to use Kaoru to take out the source of the anti-Makai barrier Pazuzu erected. As Kaoru is forced into it, Kouga battles the Horrors until he can become Garo, slaying Pazuzu after defeating him as a response to his final wish to taste Kaoru.

Remembering Kouga's words to her during the Morax incident, Kaoru decides to live in the Saezima manor's guest room to his dismay. Meanwhile, a pharmacist named Shitoshi Morino is one the run after being made a suspect in the murder of a woman named Reiko Sagashi. Kidnapping a high school girl as his hostage, he is confronted by his old rival turned cop Hanasawa. As Morino and Hanasawa get into an argument over the matter, they and the girl soon realize they are not alone in the warehouse. Arriving in the area, Kouga encounters a moth which embodies a heart-broken woman's final thoughts prior to becoming a Horror's vessel. Following the moth, Kouga learns the Horror is Lunarken, a sadistic glutton who corners her prey in order to feed during a full moon. Arriving to the warehouse and knocking the three humans out, Garo battles Lunarken and slays her. By the time the three humans came to, with no memory of the night's events, Morino is cleared of all charges against him.

Kouga hunts Horrors at a local cemetery, losing one when he is wounded by a dagger from an unknown assailant. Running into a middle aged prostitute named Kotomi, who just beat up a man and hurting two younger girls for their money, Kouga runs off after he checks her for possession and finds her clean, just as Kotomi is quickly possessed by the Horror. The next day, after getting his injury tended to and negating the poison, Kouga learns from the Watchdogs that the weapon is a Dagger of Haja which only Makai Knights would use. Meanwhile, forming a pact with the Horror inside her, Kotomi regains her youth as she starts killing off men. Meanwhile, while looking for a job, Kaoru is saved by a couple of seedy guys by a mysterious young man, whose words put her not at ease. Kaoru shows up for the job of bartender before witnessing Kotomi killing up her employer, Kotomi chases Kaoru to the harbor as Kouga appears. By then, another dagger appears belonging to the man who saved Kaoru earlier, telling Kouga he is also a Makai Knight. Annoyed, Utoque attacks as Garo battles and slays the Horror. Kotomi asks for help as she dies, but Garo says it is impossible as she allowed the Horror to possess her in the first place. Soon after, Rei formally introduces himself, before confusing Kouga and Kaoru and taking taking his leave.

Unable to find information on Rei, Kouga and Gonza speculate that he is from the western district. Kouga made arrangements for the Barankas fruit with Gonza and he heads out for his routine of sealing and entrances used by Horrors; finding that Rei has been doing his job. Kaoru gets a new job as a waitress and Rei stops where she is working for a table full of sweets. Soon after, Rei attempts to kill Kaoru in the back entrance, but Kouga appears to stop him. After having Kaoru be taken back to his manor, Kouga confronts Rei as the two fight their way through Shinjuku's Capital Building where they get a brief interference from a Horror before the two assume their Makai Knight forms. The two fight their way down the Capital Building before they run out of time with Garo the winner to ZERO's dismay.

While training, Kouga is a bit annoyed of Kaoru drawing his hand. Gonza tries to quell the situation by offering English tea, but Kouga leaves in frustration while Kaoru is wondering why she has not been able to draw lately. Meanwhile, a young barkeep named Misato Kosugawa, who became a serial killer after the suicide of her lover, ends up becoming the Horror's host to complete her collection of ideal fingers to complete a set of hands. Sensing Kaoru entering her place of business, Misato decides to kill her for her finger while Kaoru is in a drunken stupor when ZERO arrives and drives the Horror away with Kouga's aid. Assuming its true form, Moloch battles Garo and is slain with only Misato's engagement ring left. Kaoru and Kouga return home with Kaoru sketching his hands again as he rests, stating that his hands are not dirtied as she thinks about her desire to draw something important.

Kaoru is hired by school headmaster Yagi to restore a mural of a goddess her father painted years ago but no record exists of what the damaged area looked like. While purifying his sword, Kouga is sucked into an alternate reality where he meets a version of Garo. Kouga, having defeated 100 Horrors, must face an ordeal. Kouga instead tries to battle the Horror Humpty, but cannot hurt it. Kouga soon passes the ordeal and is granted the Makai Horse Gouten, which he uses to defeat Humpty. Meanwhile, Kaoru remembers her father's inspiration for the mural, and restores the goddess to her former glory.

The Horror Asmodai appears and, using his act as a puppeteer, causes groups of people to kill each other before devouring their remains. While going through her father's things, Kaoru discovers the unpublished book from her dreams with the blank page at the end of it. Asmodai strikes again before the Makai Knights eventually destroying him.

The trickster Horror Dantalian lures people to play his coin game but, when they lose in his fixed games, he devours their soul. Dantalian tries this trick on Kaoru and takes her soul. After facing off against Zero, Kouga encounters Dantalian and competes in his games to recover Kaoru's soul. He eventually succeeds, destroying Dantalian and reuniting Kaoru's body with her soul.

Gonza and Zaruba reflect on Kouga's growth as a knight, remembering him training with his father, Taiga. Out one night with his father, they encounter a Horror, with Taiga becoming Garo to destroy it. Later, Kouga witnesses his father dying at the hands of what he thought to be a Horror, though it is actually a figure named Barago. Kouga trains for years to be able to use the Garoken and fight as the new Garo, eventually becoming the man he is today.

While resting, Zero dreams of his past with Shizuka and their ill father, both of whom were murdered by an armoured figure who he comes to believe was Garo. Waking up in the present, Zero finds Kaoru visiting him but drives her away. Summoned by the Eastern Watchdogs, Zero is ordered by them to support Kouga in sealing a gateway and slaying the 100 Horrors within it. They enter the Demon Realm and eventually destroy the gateway's energy source, but Zero still has his doubts about Garo's part in his step family's murder.

After confronting the Horror Gagoiru in the west, outside his area, Kouga is ordered not to set foot in the area again. Meanwhile, during her attempt to uncover the truth behind the final blank page, Kaoru finds a clue in an interview by sculptor Kouhei Kuramachi who states her father as an inspiration to him. Entering the western territory, Kaoru finds Kouhei's studio. However, learning that Kouhei never met her father, Kaoru is forced to run for her life when she realizes he is a Horror's host. Though Zero comes to her aid, Kouhei flings her over the ledge with Kouga arriving to save her in spite of the disobeying the Watchdogs. Forced to stay at the sidelines, Kouga witnesses Zero battle Gagoiru, killing the Horror as its host was in awe of Zero's beauty. After being thanked by Kaoru, Zero walks off while revealing his true name: Rei.

Kouga arrives to the home of his father's old friend, the Makai Priest Amon. Explaining that this is a night when Horrors cannot enter their world, Amon reveals that he and Taiga played a game of Bar Chess and wishes Kouga to finish what his father started. During the match, Amon reveals he knows of Kaoru and suspects that Kouga is protecting her the same way his father protected him. However, Kouga admits he used Kaoru as a tool at first to find Horrors, but he grew to love her and is intent to save her. Impressed, Amon reveals he knows of the item Kouga intends to save her with: The Barankas Fruit within the Forest of Glen, which he intends to get for Kouga once it is ripened. Though Kouga is close to losing the game, and ten years of his life, Amon post pones the game like Taiga did years ago. But before Kouga leaves for home, Amon presents him with another revelation: the chance that his father's pupil Barago is still alive and events will unfold where he has to know who is truly friend and who is truly foe.

After telling Gonza about what Amon told him about a means to save Kaoru, still hiding the truth from the girl as he promised to protect her, Kouga learns that a Horror named Haru appeared. Entering the body of a goldfish, Haru takes advantage of a man named Tonuma to have him feed it women in order to assimulate their features to gain a human-like appearance. After being unable to find the Horror, Kouga is forced to use Kaoru as bait. But temporary halted by the other Horrors attracted to Kaoru, Kouga is barely able to get to her in time as she was about to be fed to Haru. Kouga shatters the glass with the incomplete Horror revealed as it is breathing heavily before beheading Haru and restraining himself from killing Tonuma. However Haru's head reveals Kouga's intention for Kaoru as Horror bait in its dying breath, with a heart-broken Kaoru running off.

After Kaoru runs off once learning the apparent truth that he used her as Horror bait, Kouga learns from Gonza that Amon has been murdered. Summoned by the Eastern Watchdogs, Kouga learns that a Maki Priestess named Jabi has took twelve Horror Daggers from them and was Amon's killer. However, not believing his childhood friend killed Amon, Kouga finds Jabi. Though asking why she stole the daggers, Jabi reveals that Amon was actually murdered by a rumored Horror-eating Makai Knight and that she intends to personally send the blades into the underworld. Forced into fighting Jabi for the blades, Kouga manages to restraint her. Rei, tricked by the Watchdogs to kill Kouga and Jabi for them, arrives with Kaoru as he demands the Horror blades. After tricking Rei, Kouga holds him off as Jabi takes Kaoru to a safe area.

After donning their Soul Metal Armor, Garo and Zero have an epic battle with Jabi watching as the two combatants are forced out of their armor. However, before Rei can kill a weakened Kouga, Jabi intervenes and spirits him off to where Kaoru is. After Jabi tells her that Kouga was actually trying to find a way to save her life, a confused Kaoru runs off before Gonza finds her and brings her to the cabin where Kouga spent his childhood. As Kaoru regains her faith in him, after his wounds were tended to, Kouga asks Jabi to help him enter the Forest of Glen. After revealing the legend behind the Horror-eating Makai Knight and the true nature of the Eastern Watchdogs, Jabi proceeds to perform the ritual to send the Horror Daggers into the underworld with his help. However, before she could finish telling Kouga something important, Jabi is seemingly killed by Kodama, the Watchdogs' servant. Kouga attempts to fight the stronger Kodama as they fight for the Horror blades. Rei arrives, but is unable to send the Horror Blades to the other side as they turn into a giant Horror. Neither Garo and Zero could harm the titanic Horror as the Horror-eating Makai Knight appears and absorbs the beast before taking his leave.

With time running out, Kouga leaves for the Forest of Glen. Though knowing he would die, Kouga convinces the gatekeeper Tamu to give him safe passage after she tests his character. Fighting his way though the forest's traps and many Horrors, Kouga finds Kaoru's disembodied soul and convinces her to keep on living as he entrusts Zaruba to get her back into her body while he goes to the Barankas. However, Kouga ends up facing the Barankas Fruit's guardian. Enabled by the being to assume his Makai Knight form, Garo summons Gouten to battle Grou Dragon physically and ethically. Though Rei helped Kouga at the last second, Grou Dragon accepts its defeat before dissolving. With Rei carrying him back, Kouga manages to give Kaoru the Barankas fruit just in time.

Saving Kaoru's life, she and Kouga admit they are glad of the choices they have made, unaware of what is to come. During that time, Gonza encounters a strange man who leaves him a letter, calling out Kouga to Winter Gate. Though warned that it would be trap, Kouga goes anyway. Arriving there, he is meets the man as he tells him he has until dawn to kill him. Fighting through Horror-possessed gunmen before the host appears as the Horror Bonafletz, Garo manages to strike down the Horrors before striking Bonafletz down. However, Bonafletz turn out to be security guard as the host reveals himself to be not only human, but also the father of Misato Kamisugawa, the vessel of the Horror Moloch who Kouga killed. Kamisugawa then proceeds to ask if killing those possessed by Horrors justifies the sadness their loved ones had to endure as Kouga refuses to take his life. However, revealing the Eastern Watchdogs gave him the means to enact his revenge, Kamisugawa uses the Horror Dagger holding Molch's essence on himself. Becoming Moloch, Kamisugawa realized the pain his daughter suffered as he pleas Kouga to kill him as the sun rises. Back at the manor, Karou screams in fright when a strange mark appears on her neck.

Finding Kaoru with a Horror Gate on neck, Kouga learns of the Ulimate Horror Messiah and the goal of the Horror-devouring Darkness Knight. When Karou comes to and tell her dream of a man with cross-shaped scar, Zaruba reveals the figure to be Taiga's pupil Barago who became the Darkness Knight and killed Kouga's father. The revelation affects Kouga, who self-deluded himself into thinking a Horror committed the deed, as Kaoru later requests him to kill her if it save the world. However, Kouga refuses as Barago appears and defeats Kouga and Rei. Soon after, Kaoru reveals she met Barago as a child, with Kouga realizing that Barago manipulated the chain of events leading to now. As Gonza tries to cheer Kaoru up as she blames herself for Kouga's suffering while getting original copies of her father's book, Rei suggests Kouga of joining forces to fight Barago and protect Kaoru. By then, Karou enters the sanctum of Kouga's training room as she is made familiar with Kouga's armor to ease her worry before he and Rei take their leave to fight Barago and the Eastern Watchdogs after placing barrier around the manor. Seeing the irony, Karou accepts what fate dealt her.

Arriving to find the Eastern Watchdogs gone, the three given a body to enter by Barago, they approach the Western Watchdog. Though the Western Watchdog refuses to let Rei go, he reveals the vial he found at the Eastern Watchdog Palace holds a disguise potion belong to the previous Ginga user. Back at the manor, while attempting to think up an image for the final page, Ryuuzaki arrives to take Kaoru. By the time Kouga and Rei return to the manor, it turned out Ryuzaki was actually Barago as he spirits Kaoru off. Catching up to him, Kouga and Rei assume their Makai Knight forms to battle the Darkness Knight before being defeated by him as he and his group take their leave to the site of Messhiah's summoning. Driven to save Kaoru to the point of madness, Kouga is confronted by Kodama who drove him more to the deep end with remembering Jabi's demise. Rei arrives as Garo is overpowered by Kodama in his Majuu Armored form. However, when Garo exceeds the time limit, he becomes a monster and slaughters Kodama. Garo then climbs up, as Rei manages to snap him out of it before canceling the armor. Kouga thanks Rei for saving him from himself as the two proceed into the building.

Infuriated of Kaoru's confidence that her friends will save her, Barago sends Glum after Kouga and Rei as they entered the building. As Rei is forced into a physical and psychological battle with Glum before defeated by her Beast Glum form and seemingly killed off, Kouga arrives to the ritual chamber as Barago holds him off. Karou comes to by then, possessed by Messiah as Barago is devoured by the Horror as she then uses Karou to begin the summoning process while Glum holds Kouga off. After knocking Glum out, Kouga is joined by Rei as they attempt to restraint Kaoru as Messiah uses the girl's body to fight them. But at the last second, Kouga reaches Kaoru as she loses consciousness. With Rei holding Glum off, Kouga enters through the portal to where Kaoru's conscious is before entering the realm of the Horrors to face the titantic Messiah as she pint-pointed Kaoru's body to enter the land of the living.

As Rei manages to defeat Glum with Gonza's help, Kouga is unable to slow Messiah down as he is overwhelmed by the vast number of Horrors. By then, Karou's father appears to urge his daughter to complete the painting she started. This in turn cases Garo to assume his Winged Form as he grounds Messiah while Kaoru receives closure from her parents. Catching Messiah off guard by discarding his armor, Kouga manages to put Messiah back to sleep as Karou saves him from being consumed in the blast as they return to the land of the living. However, they are followed by Barago's animated armor, the Darkness Knight Kiba. After throwing Zaruba into the magic tear in response to being unable to summon his armor, the portal expands as Kouga takes his fight with Kiba on it as the stone descends across Tokyo's cityscape with Rei brieftly joining in. Eventually, the circle comes to stop at the wharf as Zaruba comes at the nick of time with Garo's armor. After Kiba is finally slain, Kouga disarmors as Zaruba dies from overusing itself. Later, as Rei gives Kouga a newly forged Madougu, which Kouga names Zaruba, Kaoru takes her leave for Italy, giving him a new version of the Black Flame and the Golden Knight with the illustration on the final page bringing Kouga to tears