Rezel Cross features five different protagonists. Two of those protagonists are Airu and Reifa. As a child the former had to witness the slaying of his father, an archeologist by a beast. The 18-year old Airu has never managed to overcome this traumatic event and hence continues to hunt beasts. The two keys to Airu's strength are an ancient sword he inherited from his father and a mysterious power sleeping inside him. Reifa is the star of a group of acrobats. In addition to being a skilled magic user, she can also throw knives at her opponents.
Once in a millennium the Petro Comet flies by Rezel Cross' world. When certain people come in contact with a substance existing on this comet, a hidden power inside them is unleashed and they become so-called Rezel. These Rezel possess super-human strength. Those Rezel who have made contact with the mysterious substance multiple times are called Regis. Because of their extraordinary power, they were feared by the people, and hence have been almost completely wiped out.
As Rezel Cross' story begins, the Zafnam Empire launches a full-scale attack on its two neighboring countries. While its people are poor, Zafnam's authoritarian regime can rely on its superior military power. In addition to steam-powered weaponry, Zafnam has also created an army of beasts. Two of Zafnam's agents are Gaso and Derira. Both men are members of a special unit known as Rezel Command. While their ultimate goal is unknown, the job of those two enemy characters is to accompany people possessing the power of the Rezel to a special facility.
During battles, command selection is done through a system reminiscent of the PlayStation Portale's Cross Media Bar. In addition to standard attacks, Airu and Company can use powerful Rezel Arts to dispose of their opponents. To use Rezel Arts, SPs are required. While Airu's Rezel Arts are physical, Reifa's techniques are magic-based. Two characters' arts can also be combined. Once a character's SP gauge has reached a certain point, the respective character gains access to boost mode. In boost mode, the character's key stats temporarily improve and he or she is capable of inflicting more damage.