In the future, mankind has discovered a way to travel faster than light and has built colonies on thousands of planets. With humanity fading and the resources of the universe starting to dwindle, some five hundred billion humans began the long journey back home, Earth. However, humanity has outgrown its capacity to repatriate that many people and thus began the "Homecoming War," where the many factions of humanity battled for a stake on Earth. The war was long and bloody, things wouldn't subside until an authoritarian universal government by the name of the Gaia Sanction declares Earth a sacred planet, and thus forbidden for humanity to repopulate.
To prevent various factions of humanity from immigrating back to Earth, an elite wing of the Gaia Fleet was tasked to defend Earth: The Deathshadow Martyr Fleet, led by Harlock. With the assistance of his scientist friend, Tochiro Ōyama, Harlock helped saved a dying advanced alien race called the Nibelung. In return for their help, the Nibelung gave Harlock their advanced technology and helped create the four Deathshadow-class ships with dark matter engines to defend Earth. Harlock's ships were unstoppable and he successfully defended Earth from humanity's influence, until the Gaia Sanction broke their own rules.
A peace treaty was created to prevent future bloodshed from various factions of humanity, however, it was under the condition that the diplomatic elite would be allowed to immigrate. Unfortunately, this didn't sit well with Harlock as he felt it was a betrayal of what he believed in as well as the hypocrisy of the Gaia Sanction. Enraged, Harlock broke rank and killed all the immigrants and set his guns upon his own fleet. With only the Arcadia in his command, the ship was badly damaged and was being boarded. In a high-risk gamble for survival and protection of the Earth, Harlock asked Miime (Nibelung observer and engineer of his ship) to unleash dark matter upon the Earth to protect it from humanity. Sadly, the gamble was made at a terrible cost.
The dark matter was uncontrollable and it decimated the Earth and life was no longer sustainable. Engulfed in dark matter, the Arcadia managed to survive the incident, but returned out of the dark clouds forever changed. Harlock's body has been immortalized, Tochiro is now one with the ship's computer, Miime is a prisoner (for unexplained reasons) of the ship, and the ship itself emerged as a powerful supernatural pirate ship. Vowing to atone for his sin, Harlock is now a rogue pirate with a personal mission to turn back the hands of time.
100 years has passed and Captain Harlock remains at large. Gaia had covered up the real condition of Earth with a giant holographic optical camouflage to maintain their power. With his own crew of rogues, Harlock has taken 100 dimensional oscillators from the Gaia Sanction in attempts to "start over." In between, Praefectus of the Fleet, Isola, manipulated his younger brother, Yama, to help him take down Harlock. Several years earlier, Yama's desperation to maintain the beauty of their mother's favorite flower in their greenhouse caused a structural collapse. The accident paralyzed Isola and reduced their mutual childhood love, Nami, severely broken and survives through a medical pod. However, through their advanced technology, she's able to live and interact with the brothers as a living hologram. Desperate to atone for Isola, Yama agreed to infiltrate the Arcadia and its crew to stop Harlock's schemes, but things became complicated.
Yama successfully infiltrated Harlock's crew, but unknown to him, Harlock and Miime always knew he was a mole. During a mission to install the 99th dimensional oscillator, Yama learned from Kei (crew member) that Harlock's plan to "start over" is by opening the time nodes to alter history and create a better time line. The mission turned awry when they realized they landed on a giant worm and Harlock came to rescue Yama. It was then Yama was about to execute Harlock, but in a life and death situation, Yama cooperated with Harlock so both could survive and escaped the planet. Back on board the Arcadia, Harlock gave his gun to Yama, telling him to use it against him if he still wants to kill him later. Yama's undercover identity was never exposed and Harlock's words convinced Yama to follow in Harlock's plans, causing Yama to defect.
The Gaia Sanction learned of Harlock's intentions of heading towards Earth and they permitted Isola to have command over a large fleet of ships to stop Harlock. Due to Harlock's military brilliance, he single-handedly pulled advanced guile tactics to throw Isola's counter-offensive fleet off and successfully defeated the fleet. To prevent further intervention, the Arcadia held Isola and his flag ship, the Oceanus, in tow as hostages to prevent the Gaia Sanction to act. Once at Earth and passed the great illusion, the crew was horrified at what has become of their Earth. It was during this time that both Isola and Miime divulged the origins of Harlock and true nature of "starting over": Harlock intends to unlock the Nodes of Time to destroy the current universe and rebirth a new one, genesis.
Shocked by truth, Yama now sides with Isola and Harlock's own crew refuses to follow his orders. Not long after, Yama helps Isola escape and have his forces take over the Arcadia. With the ship and crew imprisoned, Isola confronted Nami for informing Yama of his tactical plans (which was used against him in the earlier battle) and her love for Yama. Nami wanted to release the hatred and anger within Isola and realized the source of his torment wasn't because of Yama, but because of her. Believing her death was the only way to help him move on, Nami enraged Isola by telling him she only loved Yama; it cause Isola to pull the plug on her pod. By the time he realized it was a ruse, it was too late and Isola watched Nami fade away, expressing her final words of love for him.
Yama later received the unfortunate news, Isola made up the excuse that Nami's intervention to help Yama caused her pod to malfunction and killed her; she left him a hologram message as her final words. Yama didn't believe that excuse for a moment and wanted to confront his brother, but the guards held him back and the hologram message played. Nami explained why she chose to love Isola over him and told him to let go of his pain and guilt; she absolved him of his actions. Haunted by Nami's death, Yama wandered at the decimated Earth only to find life still thrives there, a white flower.
The Gaia Sanction planned a public execution for Harlock and his crew, they are to be destroyed within the Arcadia by a large particle machine. However, the execution was halted when Yama appeared and released the crew of the Arcadia. Yama told the crew that he was wrong, but so was Harlock and wants to show the crew something he found on Earth. While still having trust issues with Yama, the crew had no choice but to follow his lead for freedom. At Harlock's cell, Yama reveals what he had found on Earth. The flower meant that Earth is trying to recover on its own and it might be the "starting over" that Harlock wanted. Emotionally touched at the significance of this miraculous find, Harlock believes he's found his "freedom"; Harlock intends to expose the truth of Earth and escapes with the Arcadia.
Near Earth's proximity, the Gaia Fleet intercepts the Arcadia. Using its advanced speed and firepower, the Arcadia evaded destruction and successfully destroyed the hologram emitters that falsely portrayed Earth. Yattaran (crew member) managed to hack through Gaia's networks for Yama to reveal the truth to humanity, but also conveyed a message of hope that life would continue. The exposed truth of Earth's condition took away any leverage the Gaia Sanction had over its reign. Desperate to contain the situation, the Imperial Father (leader of Gaia) decided to vaporize Earth with a powerful particle cannon called the Jovian Blaster. Isola realized the Earth would be destroyed and decided to ram across the Arcadia and have it anchored alongside each other. Because Gaia is using the Arcadia as the target, if the ship moves, Earth would be fired upon off course; Isola staged a showdown between the Oceanus's crew and Arcadia's crew.
When Yama confronted Isola, the two fought and Isola shot at Yama's face, causing him to lose his right eye and have a similar scar like Harlock. Isola would've won if it weren't the intervention of Harlock. It was then Isola warned them about the Jovian Blaster, Harlock remarked Isola kept his oath more than any one ever did for Earth. Harlock then asked Miime to unleash the full dark matter energies of the ship. When the Jovian Blaster fired, the Arcadia created a powerful shield that distorted the blast, saving Earth in the process. Yama later took Isola on board the Arcadia, as he was dying, he explained that he saved Earth because it had the flowers that Nami and their mother loved. After getting a glimpse of the flower, Isola died in Yama's arms and the Arcadia crash-landed on Earth.