It was followed by Advance Guardian Heroes on the Game Boy Advance in 2004. A remake of the original game was released on Xbox 360 in 2011 as a downloadable title.
Long Ago, a supreme being created the universe to find ultimate warriors to hire as its personal soldiers. A vicious battle was waged between the Earth and Sky Spirits (renamed the Earthblood and the Skyborn). The Sky Spirits bestowed incredible powers upon the humans, effectively making powerful wizards for their own gain. The human wizards joined the effort against the Earth Spirits, banishing them into the darkness. Soon after this was accomplished, the Sky Spirits grew fearful and jealous of the humans, and banished them all into the darkness with the Earth Spirits. Mankind instead opted for a more physical approach to life, and the Time of the Sword began.
One of the human wizards, Kanon, escapes his imprisonment with the Earth Spirits, and comes back to the surface to get his revenge on the Sky Spirits. There, he brings his case up with the existing khans. Since they do not trust him, he destroys them and replaces their kingdom with a wizard kingdom, with puppet khans to do his will. The former king prophesied, prior to his death, that should his reign and the Time of the Sword be brought to such an end, then the sword would resurface and in turn bring an end to Kanon's reign. As a precaution, Kanon banishes every existing sword in his new kingdom, but he overlooks one particular sword, belonging to a fierce, anonymous warrior who fought to the death during Kanon's takeover. Also, the former princess Serena survives the ordeal, and joins the band of knights to try to bring about Kanon's end from the inside.
At the game's start, four warriors – Han, Randy (with his pet rabbit, Nando), Nicole and Ginjirou – find the sword of the valiant warrior. Serena arrives to warn them that the knights have learned of their possession of the sword, and are coming to take it back. The four flee their home as it bursts up in flames during the invasion, then escape the town via separate ways, rendezvousing at the graveyard nearby.
The leader of the Black Knights, Valgar, awaits them there, accompanied by a powerful robotic warrior. They are unable to damage it with normal weapons, and Han resolves to use the new sword against the robot. The sword is struck by lightning, electrocuting Han and causing him to lose his grip on it. The sword then floats over to the burial mound of its original owner, who rises up in zombie form. Enraged, he obliterates Valgar's robot, and attacks Serena. However, the five discover that the warrior obeys any command that they give. They resolve that, with this new ally, the time to begin an attack on Kanon's new kingdom is at hand. They were involve ultimately fighting against the Sky Spirits, Earth Spirits, and/or the supreme being that made the universe, while others wind up with the warriors ultimately defeating Kanon, only to have to defeat Super Zur, or various rogue robotic warriors that he had left behind, led by the nefarious Golden Silver.