The lone battleship Silvana locates a Disith fleet crossing the Grand Stream and destroys several ships in a surprise attack. After the remaining Disith ships escape, the Silvana withdraws from the Grand Stream. In the frontier town of Norkia, fifteen-year-old pilot Claus Valca and navigator Lavie Head prepare their vanship for the Norkia Cup Race. On their next job call as sky couriers, Claus and Lavie accept a mission to deliver two letters to Duke David Mad-thane from his family. David, an officer in the Anatoray navy, is leading a battle against a Disith fleet at Minagith under the supervision of the Guild. After a victory in the opening engagement using musketeers, the Mad-thane fleet continues to battle the Disith in artillery combat. However, the Mad-thane fleet meets a surprise attack from a new Disith fleet as Claus and Lavie arrive on the flagship Claimh Solais to deliver the letters.

After several Anatoray battleships are destroyed, word arrives at the Imperial Capital that the Mad-thane fleet is losing the battle, prompting the Emperor of Anatoray to order an unknown asset sent to a safe place away from the Guild. As the Disith attack continues, Claus and Lavie are forced to leave the bridge, unable to directly deliver the message to David. The two soon realize that the second message tube from David's daughter Holly Mad-thane was undelivered. While David gives the order to fight to the last ship, Claus disrupts the speaker system to read the message written by Holly expressing her wishes for her father to return home. Anatoray soldiers attempt to stop Claus and Lavie, but are held back by musketeer Mullin Shetland. After hearing the heartfelt message and ridding himself of shame, David orders the fleet to withdraw. As Claus and Lavie retreat in their vanship, they are suddenly guided by a red vanship pilot to stay out of the line of fire. At the same time, the Silvana appears and fires at the pursuing Disith fleet, while the Mad-thane fleet escapes. Claus and Lavie visit Holly to bring her news of David's safety.

Since Claus and Lavie failed to participate in the time attack, they will unfortunately start in last position for the upcoming 75th Norkia Cup Race. On the day of the race, vanship courier Ralph Wednesday is wounded while being pursued by a white combat ship known as a Guild Starfish. Meanwhile, Claus and Lavie eventually pull ahead of vanship pilots Fat Chicken and Sunny Boy to challenge defending champion Hurricane Hawk towards the final stage of the race. However, as Claus takes the lead from Hurricane Hawk, Ralph's vanship crosses their path. Both Hurricane Hawk and Ralph crash their vanships into the woods, and Claus decides to pull away from the race despite being in the lead. Claus and Lavie find the dying Ralph, who is on a mission to deliver a girl named Alvis E. Hamilton. The two decide to take over Ralph's job, but are discovered by the same Guild Starfish. In order to allow Claus and Lavie to escape, Ralph acts as a decoy in self-sacrifice by detonating a bomb near the Guild Starfish. Claus and Lavie escape to the river and discover that Alvis must be transported to the Silvana into the custody of Alexander Row.

Claus and Lavie take the unconscious Alvis back to their residence. While Claus plans an escape route through the underground water canals to avoid detection by the Guild Starfish, Lavie attempts to talk Claus out of the mission and reports rumors about the mysterious Silvana. When Alvis wakes up, the two of them hide the fact that her caretaker Guita Rjuna was shot and killed by the Guild Starfish during the mission with Ralph. Later that night, while Claus and Lavie are sleeping, Alvis stumbles across a goat plushie. However, this allows the Guild Starfish to pinpoint their location and wreck the house. The three escape through the underground water canals in the vanship, and Alvis finally realizes that Guita has already died. The Guild Starfish discovers them near the end of the underground water canals and damages the vanship, forcing an emergency landing in the palace ruins outside Norkia. As the Guild Starfish captures Alvis and attempts to kill Claus, a gunshot initiated by Alexander from a distance causes the Guild Starfish to collapse.

Alexander takes the unconscious Alvis into custody and leaves with the crew of the Silvana. Not wanting to leave Alvis alone, Claus quickly repairs his damaged vanship and drains fuel from the downed Guild Starfish, but Lavie is hesitant about the decision. While in pursuit, they discover that the fuel composition was purer than what they have used before and finally suspect that the Guild Starfish belongs to the Guild. Sophia Forrester, the executive officer of Silvana, greets Alvis when she awakens. Claus and Lavie catch up to the Silvana, but it opens fire on their vanship as they attempt to board. Short on fuel, Claus is forced to make an emergency landing on the lower deck of the Silvana as it stops firing. Claus and Lavie make their way to the hangar and find the red vanship that they encountered at Minagith. They get into a fight with the flight deck crew, which includes Godwin Austin, Gale Frank, Anthony Kostabi and Ethan Pelerin. The four are stopped by Tatiana Wisla, the red vanship pilot.

Guild members Dio Eraclea and Lucciola discover the downed Guild Starfish and its dead pilot in the palace ruins. When reviewing the video records of the Guild Starfish, Dio takes an interest in Claus. At the Imperial Capital, Tatiana reports to the Emperor that Alvis has been safely delivered. Aboard the Silvana, Alvis wanders into the hangar with the flight deck crew, until Sophia reunites her with Claus and Lavie. Claus is taken to meet Alexander, who questions his reasons for protecting Alvis and his reasons for being a pilot. Before Claus can answer, they are interrupted by eighteen approaching Guild Starfish. Lavie questions the reputation of the Silvana as the safest place in the world. The Silvana, unable to effectively defend itself, is boarded by a Guild Starfish. However, Godwin destroys the Guild Starfish, while damaging Claus and Lavis's vanship. Unable to escape on their damaged vanship, Claus and Lavie are allowed to join the fight on a spare combat vanship.

The Silvana defends against the attack of the remaining Guild Starfish until they are forced to withdraw due to limited fuel. Claus and Lavie enter the battle in their spare combat vanship, but Claus struggles in maneuvering the vanship. As Claus has a better grasp, Dio observes him completing the Scissors and an Immelmann turn. Both Dio and Lucciola join the battle as pilot and navigator in two Guild Starfish combined, but Dio toys with Claus and Lavie by repeatedly achieving a target lock on them before disengaging each time. Lavie forgets to reload the ammunition and eventually suffers a redout when Claus attempts to evade from Dio and Lucciola's Guild Starfish. Midway through the battle, Tatiana returns to find the Silvana under attack and also engages Dio and Lucciola's Guild Starfish. While Lucciola disconnects his Guild Starfish to engage Tatiana, Dio ceases playing around with Claus and Lavie. However, all Guild Starfish are recalled before Dio is able to fire on the next target lock. Back aboard the Silvana, Tatiana is angry that Claus was given permission to fly a combat vanship and criticizes Lavie as a poor navigator.

The Silvana arrives at the station Casino Royale for repairs, and its crew is given temporary shore leave. At the bar, Lavie encounters Mullin, who resigned his commission on the Claimh Solais after the battle at Minagith. He intends on joining the battleship Goliath, which is also docked at the station. While a gambling bird race is going on, Count Charles Knowles, commanding officer of the Goliath, ridicules Mullin for wearing survival medals. During the final bird race, the crew of the Goliath manipulates the field with a camera flash to allow its favored bird to win. As Lavie catches the crew of the Goliath of cheating, this starts a fight between the crews of the Silvana and the Goliath. Station owner Walker breaks up the fight, but Charles challenges Alexander to a ship-to-ship duel. When both ships leave the dock, Charles realizes that he has challenged the invincible Silvana and orders his ship to begin firing before the duel commences. Unscathed, the Silvana returns fire with its newly installed weapon and sinks the Goliath in one volley. Lavie gives Mullin a self-made survival medal.

When Mullin offers to help Claus and Lavie repair their vanship, he is recruited to join the Silvana flight deck crew as a mechanic. Claus and Lavie hear from Sophia that the Silvana is en route to Horizon Cave. The two use this rare opportunity to participate in its famous eight-hour endurance race, in which participants are randomly assigned vanships and must make them airworthy in time for the race. Before the race begins, Sophia briefs Tatiana and her navigator Alister Agrew on the true objective in the race. Dio and Lucciola momentarily appear as unwelcoming race challengers to Claus and Lavie. When the race begins, Claus and Lavie's chosen vanship refuses to start on time, forcing them to join several seconds later. Dio provokes Tatiana into a head-to-head race despite Alister's attempts to remind her of their mission. As auctioneer Giancarlo opens the black market auction, Duke Henry Knowles joins Alexander and notices his disinterest towards the initial items up for bid. However, as the final item of the auction, an artifact believed to be a gateway to the legendary Exile, is introduced, Alexander opens the bid with a surprising 10 million Claudia.^{[Note 1]}

After Henry and Alexander each raise the bid price on the Exile artifact among the other auction participants, Guild Maestro Delphine Eraclea raises the bid price to 50 billion Claudia. However, Alexander is prevented from bidding anymore due to being temporarily threatened at gunpoint before the auction officially closes. Meanwhile, Tatiana and Alister pick up a cargo of explosives for their mission during their final pit stop. By pulling ahead of Dio and Lucciola in the final lap, Claus and Lavie win the race after filling up their fuel tank halfway to lighten their vanship during their final pit stop. At precisely midnight, Tatiana and Alister drop the explosives to destroy the power generators, causing a power outage. Seizing the opportunity, Alexander kills Henry's henchmen and escapes unharmed. While Delphine discover the artifact as counterfeit, Alexander learns from Graf, the steward of House Hamilton, about the Mysterion of House Hamilton, one of the four riddles with corresponding answers that will unlock Exile. Lavie confides in Claus to be his mechanic instead of his navigator for now. Dio and Lucciola, who are able to see in the darkness, offer to tow Claus and Lavie back to the Silvana.

Following Claus and Lavie aboard the Silvana, Dio and Lucciola allow themselves to be captured. At the Imperial Capital, the Emperor begins to distrust Alexander's actions and sends the Urbanus to retrieve Alvis. Dio attempts to gain trust in Alexander by telling him about the Mysterion of House Eraclea. Unfortunately, the three Guild houses holding the remaining Mysteria were purged by Delphine. While Lavie serves as a full-time mechanic for Claus, it is soon learned that Alexander appointed Claus as a supervisor for Dio. Vincent Alzey, captain of the Urbanus, requests to meet with Alexander. When Alexander asks Claus to fly escort for his flight to the meeting, Alister defies Tatiana's disapproval and offers to be Claus's navigator. Alexander informs Vincent that he will not hand over Alvis and will fight to keep her aboard. Dio and Lucciola meet Lescius Dagobert, the chief engineer of the Silvana and a former member of the Guild. Dio then finds Alvis by herself in a weight room and recites her the Mysterion of House Eraclea, after which she falls into a trance and wreaks havoc on the battleship's systems.

As the systems return to normal, Alvis awakens with no recollection of what occurred during her trance. Returning from his meeting with Vincent, Alexander orders the Silvana to intercept the Urbanus at a region of jagged rocky spires called the Dragon's Fangs. For the upcoming battle, Tatiana appoints Claus as her navigator. As the Silvana enters the Dragon's Fangs guided by its combat vanships, the pursuing Urbanus and two sister ships, the Martinus and the Julianus, seal the escape route behind them. As two more sister ships, the Georgius and the Sebastianus, are spotted further into the Dragon's Fangs, Alexander orders the Silvana to quickly ascend after momentarily being pinned by the Sebastianus. Vincent orders the Georgius to ram the Silvana, but it accidentally rams the Sebastianus instead, destroying each other. Then, Vincent orders the Martinus and the Julianus to anchor tethers to the Silvana, preparing the Urbanus to ram the Silvana. However, Alexander orders the Silvana to fire on the surrounding rocky spires, causing them to collapse and pull down the Martinus and the Julianus. The Urbanus is forced to withdraw, but the Silvana cannot detach its tethers. Tatiana and Claus watch as the Silvana sinks below the clouds.

Claus and Tatiana make an emergency landing in a desert after their vanship hits the Urbanus as the rock spires fall. Claus attempts to generate enough power for the engine of their vanship, but to no avail. While Tatiana feels despaired that she lost Alister, Claus believes that they should still look for the Silvana. Meanwhile, migrants from Disith prepare for an evacuation to Anatoray, but the migration capsules are rather unsafe for takeoff, one of which collapses to the ground. Claus learns that Tatiana comes from a noble family abandoned by the Anatoray government, during which she reached the top of her class in the military academy until she was eventually forced to discontinue her studies. Claus successfully gives the vanship enough lift to glide across the desert, allowing the two of them to head a designated emergency resort of Silvana. Upon arrival, Claus and Tatiana are captured by Disith musketeers. They escape when Dunya Scheer, a young musketeer who was guarding them, rushes to the landing field of Disith migration capsules. However, Dunya shoots her rifle in the air and cries in grief upon learning that none of the refugees inside the migration capsules survived the launch.

Lavie, who is recovering from her injuries on the shipwrecked Silvana, dreams of her childhood with Claus, who moved to Norkia and became neighbors with her. Their fathers, Hamilcar Valca and Georges Head, immediately became best friends and teamed up as vanship pilot and navigator, while Claus's mother Justina Valca treated Lavie like a daughter. Hamilcar and Georges taught Claus and Lavie the basics of a vanship. Lavie recalled a male pilot and a female navigator who were friends with Hamilcar and Georges. One day, Hamilcar and Georges received an assignment with their friends to cross the Grand Stream and deliver a peace proposal to Disith. However, Claus and Lavie soon heard the news that Hamilcar and Georges lost their lives along with the female navigator in their attempt, and Justina died six months later. After being orphaned, Claus and Lavie trained to fly a vanship, eventually selling their house to keep the vanship and training for courier missions. When Lavie finally awakens, she cries from the memories. Dio and Alister locate Claus and Tatiana near the landing field of Disith migration capsules. After reuniting with Lavie, Claus informs her that their hometown of Norkia has fallen to Disith.

Lavie chooses to avoid Claus after witnessing Tatiana wearing Claus's extra pair of overalls. Meanwhile, Vincent is stripped of his command on the Urbanus after losing four sister ships against the Silvana, and he is assigned to the fleet defending Norkia. Dio shows Claus a photo of Hamilcar and Georges with their two friends, which was found in Alexander's quarters. As repairs for the Silvana are completed, Alexander later confesses that he is the surviving pilot from the mission to deliver the peace proposal to Disith and the former owner of the vanship that Claus and Lavie currently fly. He recounts how his fiancée Euris Bassianus, Hamilcar and Georges all died, remembering that Delphine was smiling when he flew away from the Grand Stream. Claus learns that Alexander is fighting to destroy Exile, which reinforces the Guild's authority in the world. After receiving a pigeon post from Prime Minister Marius Bassianus warning of the Emperor's plans on escalating the war upon taking advantage of Disith's collapse, Sophia reveals herself as the Princess of Anatoray. Conflicted between her responsibility to the throne and her desire to stay aboard the Silvana, Sophia is comforted by Claus. She suddenly kisses Claus as gratitude.

Sophia leaves the Silvana in order to return to the Imperial Capital, which stirs mixed emotions for the crew of the Silvana. The Emperor places Marius under house arrest, after the latter pleads to spare the Disith who have lost their homes. Alexander finally considers launching a strike at the Guild. When Sophia arrives at the Imperial Capital, she is imprisoned in the tower by the Emperor for her actions aboard the Silvana against the Urbanus. She is visited by Marius, who raised her after his daughter Euris died in the Grand Stream, and he asks her to remain in the tower until after his plans for her to become the Empress of Anatoray is completed. Claus reveals to Lavie that their vanship belonged to Alexander. That evening, Commander Nestor Messina leads the Disith fleet into invading the Imperial Capital, whose defense forces are stretched thin. In the confusion, Marius assassinates the Emperor but is fatally wounded himself. Vincent heads to the tower to prevent one of the Emperor's guards from killing Sophia and takes her to safety onboard the Urbanus, taking command of the ship once again.

In the Emperor's absence, Sophia orders the Urbanus to stop General Vitellius from attacking Disith with a Scolopendra Cannon in compliance with a ceasefire. The arrival of the Mad-thane fleet forces the Disith fleet to withdraw. The following day, vanship couriers arrive with a message from Walker, who invites the Silvana to Horizon Cave for repairs and resupply. Lescius entrusts Alexander with the Mysterion of House Dagobert. Before his death, Marius also sent the Mysterion of House Bassianus to Alexander. The Silvana finally arrives at Horizon Cave, currently used as a training base for an assault against the Guild. Although the Guild suspects of a rebellion, Delphine decides not to take immediate action. At the training base, Claus meets Michael Wednesday, elder brother to the late Ralph from whom Claus took over the duty of delivering Alvis. Claus and Lavie reunite with Hurricane Hawk, Fat Chicken and Sunny Boy from Norkia after David, who was inspired by the actions of Claus and Lavie at Minagith, called for all vanship couriers to fly as fighter support.

Sophia arrives at Norkia to parley with Nestor and reveals to him a copy of the peace offer lost in the Grand Stream ten years earlier. As a gesture of goodwill, Disith supplies Anatoray with a map of the Grand Stream's air currents and a recording of the acoustic signature of Exile. Mullin decides to rejoin the musketeer squad and meets Dunya. They are informed that the capture attempt of Claudia Units^{[Note 1]} will occur on the Guild's Covenant Day, when seventeen-year-old youths pledge their allegiance to Delphine. Before the Silvana leaves dock, Claus, Lavie and Alvis say goodbye to Mullin. The formal alliance between Anatoray and Disith is signed at Sophia's coronation as the Empress. Claus, Tatiana, Dio and Lucciola arrive ahead of the Silvana to send congratulations, but Delphine's ship appears from the clouds above and rains down rose petals as a declaration of war. Realizing that he has been found by his sister, Dio panics and flies his vanship erratically. When Alexander sees Delphine's ship above the site of the coronation ceremony, he immediately orders that it be destroyed, but second officer Arthur Campbell refuses to comply for fear of killing Sophia.

After Delphine's ship leaves the coronation ceremony, the Silvana heads to the Dragon's Fangs, where it finds the Urbanus flying under the imperial banner. Sophia proposes that, using the chart provided by Disith, the two ships search for Exile six days ahead of Covenant Day in the Grand Stream. Using acoustic torpedoes and echolocation, listening officer Wina Lightning will match Exile to its acoustic signature. Sophia reveals to Claus that Alvis is the key to turning Exile against the Guild, but vows to keep her safe. Alvis finds out about the Guild's upcoming Birth Week and plans a birthday party for Dio, who does not wish to return to the Guild. At Norkia, David witnesses a Disith ship fall from the sky while delivering water to drought-stricken regions when Delphine recalls its Claudia Unit. Meanwhile, Mullin and Dunya continue their training at Horizon Cave. As the Silvana and the Urbanus enter the Grand Stream, the first acoustic torpedo is launched.

As the Silvana and the Urbanus continue their search for Exile, Sophia briefs the vanship pilots on their strategy to capture it. Sophia asks Dio to fly as Claus's navigator, but he refuses from fear of being found again by Delphine. At Horizon Cave, Nestor proposes that the Claudia Unit capture plan be accelerated after the Guild recalls several Claudia Units, but David appeases him to wait for the scheduled operation on Covenant Day. On the final day of the Guild's Birth Week, Alvis surprises Dio with a birthday party, much to his delight. After days of searching, the Silvana and the Urbanus locate Exile, and Dio agrees to fly as Claus's navigator to assist in its capture. The Guild locates Dio on board the Silvana, and Delphine orders Lucciola's brother Cicada to retrieve him at all costs. As the vanship squadron attempts to anchor cables onto Exile, the ship's defense system activates, but Dio helps complete the objective after identifying an unprotected section of the hull. Alexander hands the Mysterion of House Bassianus to Sophia and tells her to return to the Urbanus. Just before Claus and Dio return to the Silvana, Guild Starfish land on the flight deck.

Claus and Dio return to the Silvana, only to realize that the rest of the crew has gone missing. When they go to search the bridge, they find out that Delphine has captured Alvis and has commandeered the battleship. Tatiana and Alister sneak a transport carrying Sophia back to the Urbanus. Alexander comes out of hiding to attack Delphine but is defeated by Cicada. Ordering Cicada to secure Exile before she takes her leave, Delphine escorts Dio back to the Guild Fortress along with Claus, Alvis and Alexander. On the Urbanus, Vincent promises Sophia that the Silvana will be reclaimed. When Delphine shows Claus and Alvis around the palace, she explains that Dio is preparing for the Rite of the Covenant. Delphine indulges in the world's rarest delicacies at dinner, causing Claus to become upset about her disregard of the hardships of the people of Anatoray and Disith. Dio is reunited with Claus and Alvis, but they find that his personality has changed and he no longer recognizes them as friends.

After the Urbanus locates the Silvana and ensures its safety, Sophia returns and is surprised that Claus has been taken. As Covenant Day arrives, Dio takes part in the Trial of Agoon to claim inheritance of the Maestro's position by participating in mortal combat against other Guild members. Claus worries that Dio may die, unable to bear seeing him fight. At the same time, the operation to capture the Guild's Claudia Units commences at Horizon Cave. On the Silvana, Lavie finally completes the repairs for her and Claus's vanship. Delphine takes Claus and Alvis to the location of Exile, where they find its defense system has begun attacking Guild Presence Ships as well. Delphine reveals that Exile is a colony ship used by those who first settled on their world. Exile attacks Delphine's Guild Presence Ship but stops when it senses Alvis's presence. Injected with a truth serum of thorns, Alexander recites the Mysteria of House Dagobert and House Hamilton, and Alvis responds to both. However, Alexander reveals that he has not read the Mysterion of House Bassianus before entrusting it to Sophia. Delphine then receives word that Dio is the victor of the Trial of Agoon.

In a flashback, Delphine introduces a younger Dio to his new servant, whom he names Lucciola. In the present, Delphine greets Dio as the new Maestro at the Guild Fortress. Using the Urbanus as a shield, the Silvana heads into Guild territory to recapture Exile. Meanwhile, Anatoray and Disith soldiers seize the Guild's Claudia Units. In the ensuing fight aboard one of the battleships, Mullin is seriously wounded, much to Dunya's worry. Delphine learns of the uprising and recalls the Claudia Units. Lucciola, who can no longer bear to see Dio's condition, tells Claus to leave with Alvis and Dio while he covers for their escape. Before they leave, Lucciola gives Alvis a device which allows them to communicate with the Silvana. After defeating Delphine's guards, Lucciola goes to confront Delphine while also killing Cicada. Lucciola remembers that Dio had accepted him as a friend rather than a servant in their childhood. Delphine gives Lucciola a ring as a reward, only for him to disintegrate into thin air.

A portion of the Guild Fortress breaks apart and falls away from the Grand Stream into Anatoray. Claus escapes in the vanship that was previously brought with them to the Guild Fortress and takes Alvis and Dio to Norkia. Dio is then left in the care of Lady Mad-thane, who has converted her residence into a makeshift hospital for wounded soldiers. Claus takes Alvis back to his wrecked house, where they stay overnight. The combined Anatoray and Disith alliance fleet launches a surprise attack on the Guild fleet, emerging victorious with the help of the vanship squadrons. The alliance fleet continues to pursue the withdrawing Guild battleships into the Grand Stream. When Claus and Alvis are finally able to contact Lavie at the Silvana with Lucciola's communicator device, the two are told by Sophia to make a rendezvous at the Dragon's Fangs.

As the Anatoray and Disith alliance fleet and the Guild fleet approach Exile, it indiscriminately attacks them both, forcing the alliance fleet to fall back to save their remaining battleships from being destroyed. Delphine's Guild Presence Ship is still left unharmed from Exile. Claus and Alvis rendezvous at a fueling station in the Dragon's Fangs and makes the journey to the Grand Stream, switching vanships and navigators after each checkpoint until he is reunited with Lavie. After the first checkpoint with Alister as the navigator, Claus arrives at the second checkpoint with Tatiana as the navigator. On the way, Claus dogfights with two Guild Starfish. When Exile receives a pulse signal, it begins to retreat from the Grand Stream towards Disith, followed by both fleets. At the Casino Royale, the last checkpoint before the Grand Stream, Claus and Alvis reunite with Lavie, who holds the message tube containing the Mysterion of House Bassianus. They fly together in Claus and Lavie's vanship, which has been reinforced for the journey in the Grand Stream. Claus, Lavie and Alvis are then intercepted by Dio, who has run away from the Mad-thane residence in a white vanship.

As Exile enters Disith territory while continuing its indiscriminate attack, the alliance fleet loses one-quarter of its battleships, but Sophia declares to her crew that this has become a war of attrition. In the Grand Stream, Dio pursues Claus's vanship, reliving their race at Horizon Cave. However, Dio falls into despair upon realizing that Lucciola is no longer with him and is thrown off his vanship by a gust of wind. The Urbanus leads the remaining ships of the alliance fleet in protecting the Silvana as it makes a final attack to destroy Delphine's Guild Presence Ship, sadly with Alexander still held captive inside. Claus and Lavie finally cross the Grand Stream into Disith, completing the feat that their fathers could not achieve. As Alvis is brought to Exile, Claus recites all four Mysteria. After Alvis responds to each one, Exile sheds its defensive cocoon to reveal a starship, which contains the vanship and remains of Hamilcar and Georges. The world of Prester is revealed to be in the shape of an hourglass, and Exile takes Claus, Lavie, Alvis, Tatiana, Alister, Holly, Mullin and Dunya back to Earth. They all enjoy a peaceful life together with their children.

Fifteen-year-old pilot Fam Fan Fan and navigator Giselle Collette are among Sky Pirates who ride smaller vanships called Vespas. With the help of their fellow Sky Pirates, Fam and Giselle capture an Old Federal Battleship led by Ades Federation captain Ernest Cirrus Lindemann. Meanwhile at the Grand Lake, Liliana il Grazioso Merlo Turan and her younger sister Millia il Velch Cutrettola Turan, princesses of the Kingdom of Turan, prepare for a peace treaty with the powerful Ades Federation led by Premier Luscinia Hāfez, Liliana's childhood friend. However, the peace treaty is a ruse to capture the princesses while the larger Ades Federation fleet attacks the unprepared Turan fleet. The Sky Pirates learn of the attack and head to the Grand Lake. Fam offers to rescue the princesses in exchange for surrendering the flagship Lasas to them. Thanks to Fam and Giselle, along with the other Sky Pirates, the Ades Federation fleet is tricked into shooting each other due to smokescreens and faked light signals, as well as fooled into believing the Lasas has sunk. Now under the safety of the Sky Pirates, Liliana orders to head back to Iglasia, the coastal capital of Turan, to prepare for Luscinia's next attack.

While Liliana instructs Fam and Giselle to escort Millia back to Iglasia, Liliana forms an alliance with Giselle's father Atamora Collette, leader of the Sky Pirates. Liliana intends to use the Lasas in a surprise attack to scuttle the Impetus, Luscinia's flagship. After Millia sees her bedridden father, the King of Turan, he entrusts Fam and Giselle to Millia. As the Turan and Ades Federation fleets battle, Liliana's plan of action fails when Luscinia's assistant Alauda boards the Lasas, kills the crew and kidnaps Liliana. After Sky Pirate Dio Eraclea informs Millia of the abduction, Fam, Giselle and Millia sneak inside the Impetus and confront Luscinia in the command center. Liliana surrenders to Luscinia, but that does not change his vision of peace. Luscinia recites the First Mysterion of Turan, sending Liliana in a trance surrounded by light and prompting Fam, Giselle and Millia to escape. At the same time, one of the Exile colony ships, which appear as crescent moons, drops down and destroys Iglasia and its citizens, including the King of Turan. Fam and Giselle wake up after crashing their Vespa, and Millia is found mortified upon seeing the capital destroyed and blood flowing into the sea.

The Third and Fourth Fleets, led by Ades Federation generals Ōrang and Sorūsh of the respective flagships Admirari and Senapati, defeat the Notos Battleships. In Morvarid, the capital of the Ades Federation, Luscinia and generals Kayvān and Vasant report the surrender of the Kingdom of Turan to Sārā Augusta, the child empress of the Ades Federation. They explain to her that they will work hard to find all the Keys to Exile in order to reclaim the lands for their original inhabitants. At Kartoffel, the fortress of the Sky Pirates, Millia blames Fam for failing to rescue Liliana, witnessing the Lasas being sold for scrap metal. Meanwhile, Millia's butler Teddy is welcomed into Giselle's family home, where Giselle explains that the Sky Pirates are descendants of Exile immigrants, being forced off their lands by the Ades Federation. Fam obtains Liliana's chalice and reveals to Millia that she survived a vanship crash as an orphaned baby before being adopted by Atamora. Both Fam and Giselle share the dream of holding the Grand Race, an international vanship grand prix held regularly until world peace fell apart. Residents of Kartoffel perform a candlelight ritual to honor those who died in Turan.

Fam plans to steal the infamous ghost battleship called the Silvius for Millia to regain her kingdom. After Dio provides a blurry photo of the Silvius, Giselle concludes that it is a hit-and-run aircraft carrier. On the day of the operation, Fam, Giselle and their fellow Sky Pirates ride off to the Silvius, with Millia and Teddy tagging along with Dio on his vanship. After luring the Silvius into a valley, commander Tatiana Wisla and executive officer Alister Agrew ignore Fam's message for them to surrender. After various tricks fail to stop the Silvius, Tatiana chases off Fam and Giselle with her red vanship. With the Silvius escaping to the Grand Lake, Fam and Giselle take a desperate gamble by sneaking into the Silvius, but realize too late to learn that they have flown between two watertight hatches, indicating that the Silvius is also submersible. Fam and Giselle are brought to the bridge to meet Tatiana and Alister. Tatiana offers to free Fam and Giselle if they help the crew of the Silvius steal fifteen Ades Federation Battleships intact. Fam accepts her offer for the sake of helping Millia regain her authority as an exiled princess.

Millia learns from Tatiana and Alister about the deal that Fam made with them. According to Olaf, the chief mechanic of the Silvius, Fam and Giselle are not allowed to contact Kartoffel, but are allowed to use any resources aboard Silvius to help them fulfill their deal with Tatiana. As Fam and Giselle plan their first mission with the help of the crew of the Silvius, Dio admits to Fam that he is actually a scout for the Silvius. Millia is disheartened upon learning from Dio that the Ades Federation will soon officially annex Turan, but Fam reminds Millia that her homeland is anywhere where people will follow her. In their first mission, Fam, Giselle and Olaf disguise themselves as couriers for the Ades Federation and trick Ernest to leave from his outpost, allowing them to successfully commandeer the ship-of-the-line Prince of Victorius without bloodshed. Meanwhile, Millia temporarily takes over the kitchen of the Silvius, with Teddy by her side, and announces via loudspeaker that she is forming a government in exile on the Silvius as the first step in rebuilding Turan. At Morvarid, Sārā announces the Ades Federation's annexation of Turan. Later, Luscinia visits Liliana at her bedside.

Fam and Millia drop pamphlets over Kartoffel declaring the formation of the Turan government in exile. While Fam and Giselle have seven Ades Federation Battleships left to steal, Sārā organizes her generals to rule the conquered territories. Fam, Giselle and Millia head to the entertainment city of Eldorado to participate in an underground vanship race. Fam bets against Ades Federation baroness Roshanak Babar to acquire the battleship Nāhīd. However, if Fam loses, she has to give up Millia, who is currently disguised as a boy. Unfortunately for Fam, Roshanak's pilot Yashbal Anand is a former Grand Race competitor. In retaliation for the announcement of the Turan government in exile, Luscinia accuses a group of Ades Federation nobles of treason. He claims their battleships, which were previous stolen by Fam and given to the government in exile, and he orders the Extermination Squad to purge the nobles. During the race, Fam and Giselle are unable to overtake Yashbal until the final lap. Fam and Giselle win the race by jettisoning their fuel to bank around a pillar with a harpoon in order to pass Yashbal. After celebrating, Fam, Giselle and Millia return to the Silvius with the Nāhīd in their possession.

Sārā gives a public address to her subjects in Morvarid about the purge of the traitorous nobles. She then secretly confides to Vasant that she feels responsible for not protecting all her subjects. Meanwhile, Tatiana and Alister learn that the Ades Federation plans to attack the nation Glacies, located north of the Grand Lake, due to its isolationism. The Silvius heads to the border of Glacies. Fam, Giselle and Millia learn that eight battleships seized from the purge are being transported by the Ades Federation. Fam and Giselle later head to the harbor, where they are joined by Atamora's Sky Pirates. However, they fly straight into a narrow ravine and are penned in by the Third Fleet led by Ōrang. After Fam and Giselle cause a glacier to drop on the water despite the cannonry, a giant flock of grand birds flying towards an updraft blinds the Third Fleet, allowing Fam, Giselle and the Sky Pirates to escape. Atamora's Sky Pirates head home while Fam and Giselle return to the Silvius. Fam and Giselle are then followed by the First Fleet, led by Ades Federation general Sadri, who issues the Silvius an ultimatum of either surrendering Millia or be sunk.

Glacies dispatches vanships called Rocket Fighters after detecting the First Fleet and the Silvius near their border. Meanwhile, Tatiana orders her crew to prepare for battle, soon breaking through the formation of the First Fleet using a smokescreen with their deployment of vanships. After escaping the fray, the Silvius is then under heavy attack by Sadri's flagship Anshar, as they reach the mountain range near the Glacies border. Feeling responsible for the current situation, Fam asks Tatiana to allow her to fulfill their agreement by capturing one final battleship. Fam heads into battle, this time with Millia as her navigator. The Silvius blasts through a mountain into Glacies airspace, allowing the Rocket Fighters to arrive and attack the First Fleet. Fam and Millia see a damaged Rocket Fighter, piloted by Primula and navigated by Magnolia, and use their Vespa to support it until the two regain consciousness. After Fam flies towards the underside of Anshar, Millia disables its Claudia Unit with one shot, forcing the crew to abandon ship. With the resulting capture of their final battleship,^{[Note 2]} Fam and Millia return to the Silvius with a heroic welcome. Giselle breaks down in tears upon seeing Fam and Millia return.

Dio returns to the Silvius in order to give flowers to Fam for her birthday but cannot find her. Giselle prepares to return to Kartoffel now that she and Fam have fulfilled their contract with the Silvius. Fam finds Dio as they head to the site to repair and extract the Anshar. Fam confides in Dio that she took Giselle for granted and never consider feelings. Dio tells Fam that he behaved the same way with his late navigator, expressing regret about it. Feeling responsible for the animosity between Fam and Giselle, Millia tries to help fix it and accompanies Giselle to a market. Remembering Dio's advice, Fam starts an impromptu hockey game with the mechanics of the Silvius on the deck using brooms. After returning to the Silvius, Giselle reminisces the childhood she had with Fam, realizing that Fam will always be like a sister to her. Giselle, Millia, Tatiana and Alister then join in the hockey game. The crew of the Silvius later celebrate Fam's birthday and officially accept Fam, Giselle, Millia and Teddy as part of their crew. However, they receive a surprise visit from Vincent Alzey, the Commander-in-Chief of the United Kingdom of Anatoray-Disith Vanguard Unit.

Both Giselle and Millia write a letter to Giselle's parents at Kartoffel, detailing their adventure with Fam thus far.

At the Hole of the Grand Lake, the alliance between Turan and the United Kingdom of Anatoray-Disith is commemorated. During a celebration, Atamora suggests to Vincent that Glacies should join their alliance. Meanwhile, Dio introduces Fam, Giselle and Millia to Alvis E. Hamilton, who can control the Anatoray-Disith Exile. Since Millia has not gained this ability through her family line, it confirms that her sister Liliana is still alive. The Impetus, flying the Turan flag, approaches the Silvius. Liliana declares herself as the Queen of Turan that she made peace with the Ades Federation. Luscinia then tells Tatiana to relinquish control of the Silvius within ten minutes in exchange for forgiveness of their terrorist acts. Liliana threatens to disinherit Millia, leading Fam to believe that Liliana is being manipulated by Luscinia. As Liliana orders the Turan Fleet to open fire on the Silvius, Ōrang also orders the Third Fleet to attack Kartoffel. Vincent escapes with Alvis on the Urbanus to withdraw. The Extermination Squad infiltrate the Silvius and shut down the Claudia Unit, forcing Fam, Giselle and Millia to escape as the Silvius sinks into the Grand Lake. Three Ades Federation vanships then chase Fam's Vespa in hot pursuit.

Ten years ago, Farahnāz Augusta, former empress of the Ades Federation, opened the first Grand Race to celebrate world peace. Farahnāz, who had Luscinia and Alauda as bodyguards, greeted the King of Turan, escorting his daughters Liliana and Millia. Meanwhile, Fam and Giselle came to see the race to support Atamora as the navigator for his pilot Kaiser. Liliana later developed a crush for Luscinia after he helped her up from a fall. Farahnāz, Luscinia and Alauda witnessed Vasant being harassed by other Ades Federation soldiers for being chosen to present the bouquet to the winners of the race, despite her being annexed from her homeland Chaos. Atamora and Kaiser won the Grand Race in the end, inspiring Fam to participate someday. During the award ceremony, a group of Exile assassins attempted to kill Farahnāz to avenge their deceased comrades. Although Luscinia and Alauda did their best, Farahnāz shielded Liliana from being shot by an assassin, causing Farahnāz to die. After Luscinia exacted violent retribution on the remaining assassins and lost his left eye in the process, Alauda subdued Luscinia from harming Liliana. In the present, Fam wakes up beside Giselle and Millia aboard a snow truck heading towards Glacies.

In the United Kingdom of Anatoray-Disith, the Urbanus is attacked by the Extermination Squad, but Dio manages to kill them and escapes with Alvis in his vanship. Fam, Giselle and Millia discover that they had crash-landed in Glacies and were rescued by Glacies pilot Dyan, who has provided them a cabin for shelter. With Millia acting as a Glacian translator for Fam and Giselle, Dyan owes them for saving her comrades during the previous battle. In Morvarid, Luscinia plans an invasion of Glacies, instructing the provincial fleets to lead the vanguard. Dyan provides necessary tools to repair Fam's Vespa, which has Dyan curious about its craft. At a hot spring, Fam tells her dream to reinstate the Grand Race, but Dyan says that the assassination of Farahnāz convinced Glacies into isolationism. The next day, Dyan finally experiences an open-air flight with Fam in her Vespa. Afterwards, Dyan departs to her base in her Rocket Fighter, predicting that they will never cross paths again but hoping that they will share peaceful skies. Fam, Giselle and Millia leave Glacies to locate the Silvius. However, they encounter the Ades Federation fleets approaching Glacies.

Fam, Giselle and Millia fly back to Glacies as soon as possible to warn Dyan. The Ades Federation provincial fleets begin their invasion, only to be quickly destroyed by the Rocket Fighter squadrons. Fan and Millia manage to warn Dyan, but the Third and Fourth Fleets shred the Rocket Fighter squadrons with auto-cannons. With only a few Rocket Fighter squadrons left, Dyan tells Fam, Giselle and Millia to leave Glacies, while the squadrons take on the fleets. Kayvān of the Second Fleet heads towards the capital stronghold of Glacies. In Morvarid, fearing the war will brand Sārā as a mass murderer, Vasant just learns that the provincial fleets died during the invasion. With the Second and Fourth Fleets destroying their ground defenses, the leaders of Glacies activate the Glacies Exile as their final weapon, which is revealed to be the stronghold itself, decimating the Second and Fourth Fleets. Fam, Giselle and Millia arrive at a nearby Sky Pirate settlement called Spargel to refuel, but they find it bombarded and abandoned due to the work of the Ades Federation long-range auto-cannons. Luscinia summons Liliana to activate the Turan Exile in order to attack and destroy the Glacies Exile.

The surviving Adamas Squadron is approached by Vasant, who is now firmly opposed to Luscinia's callous treatment. She offers to help the Adamas Squadron fight back. Fam, Giselle and Millia return to find Kartoffel badly damaged from the bombardment, but the Sky Pirates are still fine and busy rebuilding their home. After Millia makes plans to steal the Anshar and fly to the United Kingdom of Anatoray-Disith to gather more forces, she declares her vow to kill Liliana. Meanwhile, Luscinia orders Sadri to invade the United Kingdom of Anatoray-Disith in one week and leaves to fulfill a secret mission. The Ades Federation generals are concerned about Luscinia's odd behavior, highly uncomfortable about his willingness to use the destructive power of the Exile. Fam challenges her friend Fritz to a vanship race. Millia remembers that she wishes to make everyone smile just as Fam does, reconsidering her plans to kill Liliana. After the race, Millia receives a letter written by Sārā, who has dropped her support for Luscinia and advocated a ceasefire regardless of national allegiance, asking Millia to join a coalition to defeat Luscinia. Millia surmises that this decision was spurred by someone in the Ades Federation against Luscinia.

Luscinia continues his mission with Liliana and Alauda despite being informed that Vasant is plotting a rebellion. In the United Kingdom of Anatoray-Disith, Vincent muses how Sārā had beaten him to forming a coalition called the Joint Forces. Fam, Giselle and Millia visit Morvarid on a diplomatic mission to meet Vasant, who justifies that Luscinia has tyrannically betrayed the peaceful wishes of the late Farahnāz. As Fam, Giselle and Millia later try to greet the Adamas Squadron, Dyan says that she cannot be friends with the sister who is responsible for the destruction of the Glacies Exile. Ōrang and Sorūsh receive orders to reclaim Boreas, a fortress outpost between the Ades Federation and Glacies. Vasant explains to the leaders of the Joint Forces that they must defend Boreas from Luscinia. Fam accosts the leaders on their desire for revenge instead of their focus for world peace. Fam and Giselle later befriend Sārā after she expresses her desire to reinstate the Grand Race. When Sārā takes Fam and Giselle to see a portrait of Farahnāz, Sārā admits that she does not want Luscinia and Vasant to fight anymore. Luscinia, Liliana and Alauda find and unlock the Grand Exile near Boreas.

Dio and Alvis reminisce about their home world Prester, divided into two nations called Anatoray and Disith. They think back to when they each met vanship pilots Claus Valca and Lavie Head, who joined Alexander Row, captain of the Silvana. Dio recalls Maestro Delphine Eraclea, his older sister and leader of the Guild, who sought Alvis as the Key to the Anatoray-Disith Exile. Dio's best friend Lucciola was also reintroduced, and he later sacrificed himself to save Claus, Alvis and Dio, shortly after Dio was driven insane by Delphine. Anatoray and Disith united against the Guild and defeated Delphine. Alvis activated the Anatoray-Disith Exile, using it to transport some of the people of Prester to Earth and start a new world with peace. In the present, Alvis laments that there is still world conflict, but Dio encourages Alvis to live on. Dio and Alvis are later chased by Guild Starfish, which Dio declares that he will protect Alvis as he had promised Claus. Meanwhile, on a mountainside, Lavie heads to her vanship to cheerfully collect a sleeping Claus from the cockpit with a wheelchair.

Ōrang and Sorūsh discuss the controversy of waging war on former allies in order to achieve peace. The Joint Forces head towards Boreas, where the Third and Fourth Fleets are waiting. Vasant holds a neutral meeting with Ōrang and Sorūsh, as she plans to use Sārā as a metaphorical human shield in the line of fire. Shortly after, Ōrang expresses hesitancy to attack, while Sorūsh says that Sārā can be replaced if necessary. As the battle commences, the Fourth Fleet charges at a narrow pass after Vasant's flagship, the Anaitis, while the Sky Pirates fail in their attempt to capture Sorūsh's flagship, the Senapati. In the past, Ōrang became a soldier because he had genuine faith in Farahnāz's ideals for the future, while Sorūsh just became one for the glory. In the present, Ōrang recovers his loyalty and opens fire on Sorūsh. Praising Ōrang for sticking to his beliefs, Sorūsh gives the Fourth Fleet the final order of joining him in a suicidal charge towards the Anaitis. However, Ōrang destroys the Senapati, which crashes into the valley below. Meanwhile, Luscinia, after reciting the Mysteria of the Grand Exile, tells Alauda that they are following the strategy laid ten years ago.

Fam, Giselle and Millia are informed by Dio and Alvis, upon their return to Boreas, that they managed to escape from the Extermination Squad, since Luscinia is searching for the Key to the Anatoray-Disith Exile. Ōrang has joined the Joint Forces, but Dyan holds a grudge for his role in the destruction of Glacies. On a scouting mission, Fam and Giselle spot the First Fleet preparing to attack. The Joint Forces dispatch the Third Fleet and the Adamas Squadron in a counterattack. However, Sadri transmits a signal to Ōrang's flagship, the Admirari, to order a pincer movement, causing mass confusion and friendly fire between the Third Fleet and the Adamas Squadron. Fam blocks Dyan from firing at the Admirari, pointing out to her that Ōrang did not return fire. The Silvius timely emerges from the Grand Lake and ambushes the First Fleet, in which Sadri demolishes several of the cliffs surrounding Boreas, filling up some of the crevices and allowing his battleships to escape. Sārā writes letters for a truce and asks Fam and Millia to deliver them to Sadri and Vasant, respectively. Both Sadri and Vasant agree to the truce. Fam and Giselle celebrate that the war is over.

A conference presided over by Sārā is held between the Joint Forces and the Ades Federation loyalists with the aim of discussing a peace treaty between both sides. Luscinia reveals that his cause is to help pass limited resources to the next generation. Spurring into a giant argument between both sides, Sārā orders them to stop, as she does not want anymore fighting. The supporting notion convinces Luscinia and Vasant to make peace. Later on, Millia is secretly taken to a group of Turan army rebels led by Geeth, who wants Millia to overthrow Liliana from the throne for betraying Turan. However, Geeth and his men are apprehended by the Extermination Squad, while Alauda brings Millia to the Ruins of White, the former headquarters of the Guild. Luscinia invites Millia to meet with Liliana, who admits that she will be branded as a witch if she continues preserving the world by betraying Turan. Millia lets go of her anger and respects Liliana's priorities. The next day during the peace ceremony, Dyan attempts to kill Luscinia, but Liliana takes the shot instead. While Luscinia grieves of losing Liliana, Millia faints after the ability to control the Turan Exile transfers to her.

In the past, Luscinia brought Liliana to Iglasia after its demise. Liliana wanted to kill Luscinia and avenge her father, but Luscinia said that it would only lead to a massive civil war, leading Liliana to join Luscinia's cause instead. In the present, the death of Liliana impacts Millia and Fam. With the truce now deemed a failure, Luscinia and Alauda enact their final plans. The First and Second Fleets suddenly depart, much to the confusion of the Joint Forces. Aboard the Silvius, Alauda and the Extermination Squad attempt to kidnap Alvis, but Dio kills Alauda. Meanwhile, Luscinia carries Sārā in his arms, as he kills Vasant in the process. While Luscinia takes Sārā to Northern Glacies, the First and Second Fleets prevent the Third Fleet from going after Luscinia. Fam and Giselle vow that they will help Millia any way they can. After arriving at the Ruins of White, Luscinia recites the Mysteria of the Grand Exile to Sārā, revealing that she is the Key to the Grand Exile. As it takes off, Luscinia activates its powerful beam cannons many miles away from the battle zone. The Sky Pirates witness the destruction of both the Second and Third Fleets.

Luscinia demands the world to either surrender or be destroyed. The Joint Forces quickly regroup and plan their attack. Millia asks Dyan to participate in the mission by acting as Alvis's pilot, since Alvis can sense Sārā's location. With Tatiana and Alister leading the vanship squadrons, Millia takes command of the Silvius. As the Joint Forces attack, they meet stiff resistance from the First Fleet and the Grand Exile itself. However, Sorūsh reappears with the Fourth Fleet, revealing that he is still alive and sides with the Joint Forces. Luscinia fires a laser beam from the Grand Exile at Iglasia, forcing Millia to sacrifice the Turan Exile by using it as a shield. Meanwhile, the vanship squadrons manage to infiltrate the Grand Exile after the Silvius breaks through an opening in the hull. The United Kingdom of Anatoray-Disith Fleet, led by Vincent and Sophia Forrester, also arrives, turning the battle in favor of the Joint Forces. While the Urbanus and the Silvana also enter the Grand Exile, all of the vanships break off to engage the Guild Starfish. Continuing on to find Sārā further inside the Grand Exile, Fam and Giselle finally meet and confront Luscinia.

As the battle continues, Fam and Giselle attempt to convince Luscinia to surrender. It is due to Fam's moving inspiration to reinstate the Grand Race and achieve a peaceful world that finally convinces Luscinia to return Sārā back to Fam and Giselle. However, since the Grand Exile was originally left unfinished, it starts to collapse, and Fam suspects that Luscinia planned everything from the very beginning. Luscinia stays behind and eventually dies from falling debris, while the Joint Forces quickly escape from the collapsing Grand Exile. Sadri orders his remaining forces to abandon ship and surrender to the Joint Forces, instructing his first mate Guzel to deliver a locket of his daughter Rahā to Fam, certain that Fam is his granddaughter. Fam and Giselle manage to escape and return Sārā safely before the Grand Exile crashes. The nations of the world declare peace and disarm their forces, in which Ōrang is made the new premier of the Ades Federation. Guzel delivers Fam the locket, but Fam breaks down in tears over not getting to know more about her grandfather Sadri and her mother Rahā. Millia and Sārā later organize a second Grand Race to finally celebrate world peace once again.