It starts with Sash Lilac and Carol Tea rescuing a turtle-shelled, duck-billed creature named Torque in the mountains after he crash-lands from parts unknown. Lilac offers to help rescue the Kingdom Stone, a very valuable relic that contains untold amounts of energy. In doing so, they become embroiled in a brewing conflict between three nations of their planet, Avalice: Shuigang, which has become aggressive and warmongering following the sudden death of their King and the rise of his son, the mentally unstable Prince Dail; the city of Shang Mu, whose wealth-obsessed leader Mayor Zao is desperate to solve a recent energy crisis; and Shang Tu, an air city whose Royal Magister is not well-versed in war.
Lilac and Carol rush over to the ancient temple in an effort to protect the Kingdom Stone, only to be briefly stymied by Shang Tu's officers, General Gong and Neera Li, who refuse to believe their claims of a plot to steal the stone. However, they arrive just in time to watch the Kingdom Stone being stolen by Spade, a professional thief and assassin, Dail's half-brother, and Lilac and Carol's sworn rival. Spade is stealing the Stone for Mayor Zao as part of his own plan to discover the truth of his father's murder. The theft of the stone causes a cave-in, which briefly separates Lilac from Carol, who was trapped inside. However, she is saved by a young, orphan hound named Milla Basset, who had been tailing the pair with the intention of meeting a dragon.
Earlier on, Milla is first seen gathering ingredients for a "Super Feather Potion" along with Mr. Stumpy, a tree stump with a face carved into it. Milla vows to fly high, reunite with her parents and "live happily ever after, like in the stories". But the moment was ruined when the Shang Mu truck drives by, and Lilac is seen chasing after it. Milla, who always wanted to meet a dragon, follows her to the ancient temple. In the cave section, she saved Carol's life, who had been trapped inside the cave and pinned by rubble. Milla later meets Lilac outside the cave and she formed a friendship with her and Carol.
Later that night, Carol discovers that Torque is not who he claims to be; when she and Lilac press him on it, he reveals that he is, in fact, an alien sent to Avalice to apprehend an intergalactic warlord, Lord Brevon. Brevon crash-landed on Avalice after a fierce battle, and is working on getting his dreadnought operational once more. Towards this end, he invaded Shuigang, murdered its king, and brainwashed Dail to do his bidding, convincing him that Mayor Zao was the murderer and getting him to declare war on Shang Mu. Brevon intends to use the chaos of the war as a distraction so he can steal the Kingdom Stone for himself, use its energy to power his space fortress to continue his galactic conquest. Lilac is incredibly receptive to Torque's tale, and she, Carol and Milla all agree to help Torque reclaim the Kingdom Stone and stop Brevon's plans before it's too late.
The next morning, the Royal Magister, having been informed of the theft by General Gong, sends Lilac's group to recover the Stone from Zao. Arriving in the commercial district, the group is confronted by Spade, who reveals his that true allegiance in the Kingdom Stone theft was to his brother Dail and not Zao, and Serpentine, a snake with mechanical arms who serves as Brevon's chief enforcer. After finishing off the Robopanther from outside the Shang Mu mall, they arrive too late once again; Dail and Brevon's forces effortlessly steal the Kingdom Stone from Shang Mu and fly off. They meet with Mayor Zao of Shang Mu and try to convince him to work with Shang Tu and the Magister in recovering the Stone; with some appeals to his desire for glory, he eventually agrees, sending them off in one of his airships, in the direction of Shang Tu. Shuigang's airships attempt to intercept and shoot down their airship, but are beaten back.
The group finally returns to Shang Tu to report their findings, bringing along a piece of one of Serpentine's machines, made of materials uncommon on Avalice, as evidence of an otherworldly plot. Neera Li, having been suspicious of Lilac and Carol from a few nights prior, instead accuses the pair of being behind the Kingdom Stone's theft, pointing out Lilac and Carol's past as professional thieves and how they always seem to be around when trouble strikes. Although skeptical of their guilt, the Royal Magister decides to have them detained for further questioning. Milla was suddenly brought back in by Neera after her failed attempt to escape, Lilac convinces the Magister to let Torque go alone by falsely pleading guilty to Neera's claims. They effortlessly break out of jail themselves in an attempt to catch up to Torque, but are too late once again; Torque is captured by Brevon and Serpentine and whisked away.
With the Kingdom Stone and their friend in enemy hands, and no leader on Avalice to call an ally, the stress causes the remaining trio's relations to break down; Lilac wants to rescue Torque and help him complete his mission as it's the right thing to do, while Carol just wants to lay low and spend her life with her best friend rather than keep risking her life, and storms off. Convinced by Carol's pleas that she's been recklessly endangering her friends, Lilac sends Milla off to go with Carol, and heads off to save Torque herself from Brevon's nerarby base. Unfortunately, she underestimated Brevon's security, and is ambushed by Serpentine and Brevon himself, and ends up captured. Brevon, concerned that Lilac's determination poses a severe threat to his plans, and determined to make Torque reveal if there are any more Chasers, subject her to brutal electric torture.
Meanwhile, Carol and Milla find Spade in the Red Scarves' hideout and convince him of Brevon's existence; the three then storm the base and rescue Torque and Lilac. Brevon manages to catch all of them in the torture room; however, the base suddenly begins to implode, and the heroes make their escape. The group ends up separated once again in the ensuing chaos. Lilac is found by Neera Li, who arrests her and brings her back to Shang Tu. Milla, Torque and Carol meet up with General Gong and the Shang Tu truck, who were about to attack Shuigang's forces. Carol suggests that they persuade the Shang Mu army. At first, Gong refuses the idea, then he quickly changes his mind and goes after the Shang Mu army along with the trio. Back in the Shang Tu royal palace, the Magister reveals he'd had the composition of the mech investigated in the interim, proving Lilac's initial claims of innocence true. However, because Lilac had lied to him to get Torque released, he has one last task for her before he agrees to give her aid. After he had healed her via a magical sauna, the Magister sends Lilac to investigate a nearby lagoon, where a similar metal had been discovered.
Lilac discovers that the source of the metal is a strange robot similar to Syntax, Brevon's faithful AI assistant, called Pangu. Pangu reveals that the Kingdom Stone was, in fact, a gift to the three kingdoms given by a race of alien dragons that had crashed on Avalice centuries ago. It is also revealed that unless the Kingdom Stone is returned to its resting place, it will self-destruct, along with the energy the three kingdoms desperately need to survive.
Lilac reports her findings to the Magister, who reveals that Zao, determined on recovering the Stone, is leading his army against Shuigang's. She uses the Holodragon to convince the two armies to form a truce. At the Snowfields, the Shang Mu and Shang Tu armies are about to attack when the Holodragon suddenly appears, Lilac herself was seen on it, and Torque, Milla and Carol were all glad about her return.
The combined armies quickly move against Dail and Brevon's army, which has also begun its advance as Brevon prepares his fortress for takeoff. While Carol, Milla and Torque fight on the ground with Zao's tanks, Lilac uses the Holodragon to engage Syntax in an aerial battle, ultimately destroying her. At the foot of Brevon's fortress, the team confronts Dail, destroying his final mech. The mad prince attempts a final attack, but is stopped by Spade. As Spade goes to face off with his half-brother, Brevon announces that his fortress is ready for takeoff, and the team moves for the final battle.
Inside the fortress, the team faces off against the full brunt of Brevon's army, including an upgraded Syntax, and a final battle against Serpentine, who mutates into a giant monster before being subdued. In a final act of desperation and cruelty, Brevon captures Milla and turns her into a bio-mechanical monster and has her attack the team. They are forced to subdue her. Milla miraculously survives, but falls into a death-like coma. Enraged, Lilac and Carol storm Brevon's final defenses and confront the alien overlord himself.
After a fierce, chaotic battle, Brevon is ultimately defeated, but the Kingdom Stone is destroyed in the process. The team quickly escape Brevon's fortress just before it crashes into the frozen wastes. Back at base camp, Milla awakens from her coma. Lilac is distraught over the loss of the Kingdom Stone and failing to stop Brevon from escaping. Just as all hope seemed lost, the sky is suddenly lit up by a swirling vortex of crystalline energy. Realizing that this is the new form of the Kingdom Stone, the three kingdoms resolve to share the Stone's energy equally amongst themselves, bringing an end to the war.
The story ends with the Royal Magister musing that while peace has mostly been restored, there is still much work to be done. The three kingdoms work to dispose of the remaining mutants and robots that still roam the land, and while he is assumed dead, Brevon is nowhere to be found. Later In Dragon Valley, Torque says his good-byes to Lilac, Carol, Milla and Gong, thanking them for helping him. The girls and Gong go up to the balcony of the Treehouse to watch as Torque's rocket blasts off into space, holding on to the hope that he may come back someday.
When playing as Milla, her ending plays out differently from Lilac's and Carol's. Instead of being captured and turned into a monster by Brevon, Milla stumbles upon Torque overlooking an unconscious Carol. Milla learns from Torque that Brevon came out of nowhere and ambushed Carol, and Torque needs to take her back to the surface to prevent her death. Also learning from him that Lilac went to stop him alone, Milla decides to help Lilac in her fight and manages to convince him that she can do so. Torque asks her to keep an eye on her friend, and she agrees.
After storming Brevon's final defenses, Milla finally confronts the alien warlord himself. She asks him where Lilac is, after which he responds that she challenged him to a fight and that she believes he killed her when he tells her that she won't be seeing her again. He demands Milla to leave, but she refuses, and from there, a battle ensues against the Absolution and Power Suit.
Milla manages to severely damage both the Absolution and Brevon's Power Suit. Now enraged, Brevon attempts to strangle Milla, which is prevented by Lilac, who turns out to have survived their fight. Lilac then proceeds to severely beat up on Brevon, shouting at him not to hurt Milla much like she did in her own story. After the heroes and Brevon escape the doomed Dreadnought, Milla, having quickly recovered from Brevon's attempt to strangle her, joyfully alerts Lilac and Torque that Carol is alright. When Lilac and Milla ask Carol how she feels, she, in a comedic fashion, blurts out her belief that she died from the ambush. Lilac replies that Carol is indeed after all. When the Wildcat asks if they won, they answer yes, much to her relief.
Afterwards, the same ending scenes play after the scene in inside of the medical tent play out, starting with the heroes looking up at the new form of the Kingdom Stone, moving on to the Magister musing about new opportunities, the three kingdoms resolving to share the Stone's energy, monsters still roaming the lands, and Brevon being nowhere to be found, and finally ending with Torque saying his goodbyes to Lilac, Carol, and Milla.