All'inizio furono gli Dei a creare il mondo di Legaia, crearono poi gli uomini. Dopo qualche tempo le divinità notarono che i loro figli prediletti finivano spesso per esser attaccati e sopraffatti dalle bestie. Preso atto della situazione, vennero così creati i Seru: esseri in grado di fondersi con gli umani e, agendo da simbionti, potenziarne le capacità fisiche e mentali. Tutto andò bene per un bel pezzo e, con l'aiuto dei Seru, la razza umana prosperò e si ritagliò uno spazio all'interno dell'ecosistema di Legaia. Fino a quando un giorno giunse nel mondo una strana nebbia che aveva come effetto quello di trasformare i Seru in mostri assetati di sangue. Da aiutanti e fedeli alleati i Seru divennero dei parassiti che si impadronivano della volontà dei loro proprietari e li utilizzavano per azioni malvage. I pochi uomini che non avevano fatto affidamento sui Seru si rifugiarono così in zone irraggiungibili dalla nebbia e cominciarono una vita di stenti.
Le vicende del gioco prendono vita in questo momento, impersonando dapprima il giovane Vahn, un ragazzo di Rim Elm in procinto di divenire un cacciatore ed un adulto a tutti gli effetti, il quale si troverà a dover difendere il suo villaggio dall'attacco del malvagio Zeto che, aiutato da un enorme mostro, distrugge il muro di cinta e permette alla nebbia di penetrare a Rim Elm. Riuscirà nel suo intento grazie alla fusione con un potente e antico Ra-Seru, un simbionte immune all'effetto della nebbia; deciderà poi di voler eliminare della faccia di Legaia la nebbia. Durante il suo tragitto incontrerà altri due alleati: la giovane Noa e il forte Gala.
Sebbene la trama possa risoltare a volte banale, il vero punto di forza di Legend of Legaia è da ricercarsi nelle meccaniche del combattimento: una volta iniziato uno scontro potrete selezionare liberamente nella barra dell'attacco (che aumenterà di capienza man mano che salirete di livello) un colpo a scelta tra un pugno destro, uno sinistro, un calcio alto ed uno basso. Formando cosi infinite combinazioni si possono sbloccare ulteriori tecniche segrete estremamente potenti. Inoltre il sistema delle magie è stato cosi introdotto: ogni qual volta incontrerete un Seru sul campo di battaglia (riconoscibile tramite un simbolo elementale) potrete assorbirlo mediante il Ra-Seru dopo averlo eliminato. Da quel punto in poi, la magia ad esso correlata entrerà a far parte del vostro armamentario di incantesimi, e potrete utilizzarla liberamente durante gli scontri.
