Set in the year 2199, an alien race known as the "Gamilas ("Gamilons" in the English Star Blazers dub) unleash radioactive meteorite bombs on Earth, rendering the planet's surface uninhabitable. Humanity has retreated into deep underground cities, but the radioactivity is slowly affecting them as well, with mankind's extinction estimated in one year. Earth's space fleet is hopelessly outclassed by the Gamilas and all seems lost until a message capsule from a mysterious crashed spaceship is retrieved on Mars. The capsule yields blueprints for a faster-than-light engine and an offering of help from Queen Starsha of the planet Iscandar in the Large Magellanic Cloud. She says that her planet has a device, the Cosmo-Cleaner D (Cosmo DNA), which can cleanse Earth of its radiation damage.
The inhabitants of Earth secretly build a massive spaceship inside the ruins of the Japanese battleship Yamato, the Space Battleship Yamato for which the story is titled. Using Starsha's blueprints, they equip the new ship with a space warp drive, called the "wave motion engine", and a new, incredibly powerful weapon at the bow called the "wave motion gun".