It has been a few years since the conclusion of the events of the original story.
Each of the various characters has gone one with their lives.
Sabin now acts as a guard-for-hire; courier who travels about helping those in need and carrying parcels through dangerous lands.
Celes has been appointed to be in charge of the defenses of the rebuilt city of Figaro and has gotten married to Locke.
Locke is a liaison between the throne and the normal people; using his ability to blend in to insure that he can gather information about the state of affairs in the world and make certain that the needs of the people are being met.
Cyan has learned of the possibility of reviving his family and has gone looking for that.
Terra is now the mayor of Mobliz; but remains alone.
Edgar has returned to rule Figaro; attempting to assist with the rebuilding of the world that Kefka nearly destroyed.
Setzer has established himself as the premier constructor of airships and has made a fortune supplying them to various areas.
Relm and Strago along with the other survivors from Thamasa have moved back to the mainland and begun establishing a new settlement.
Shadow may or may not be dead.
Gau has returned to oversee the Veldt and see that it remains pristine,
(Non-human characters like Mog, Umaro and Gogo weren't included.)
At the start of the story; Sabin is on his way to deliver a message for Edgar to Terra and encounters a wounded traveler nearby.
Taking him back to Mobliz; the traveler mysteriously seems to have retained the ability to use magic and his presence is reawakening that skill in those he encounters.
Remembering only his name; Fayn Reij, he asks for help in curing his condition.
Since many of the world's best doctors have flocked to Figaro in the aftermath of the conflict and from there traveled around the world to help those in need; Sabin offers to escort him there. Terra elects to come along, intrigued by the mystery of this stranger.
They encounter opposition on the way when a monster attacks them in the Figaro cave; a strange being that seems to be a hybrid of Esper and beast.
Upon reaching Figaro, they find the city in chaos due to the fact that Edgar has fallen desperately ill(petrified} and none of their skills can save him.
A possible remedy was reported in the town of Zozo; but the expedition there hasn't returned.
Sabin stays behind to watch over his brother while Celes joins you to check on a group of soldiers who went missing north of Kohlingen.
Upon reaching that town, they learn that the missing men were slain by more of these creatures; but that a relic that lies in Daryll's Tomb is apparently poisonous to them and they go to retrieve it.
After taking care of that town, Celes returns to Figaro to manufacture more of the substance the relic is made of while her husband Locke joins your party to make sure that you successfully make your trip south.
The group eventually reaches Mount Zozo and defeats another powerful creature there.
A test of a sample of something else which had been affects like Edgar shows that it would work on him and they head back to Figaro.
Upon saving Edgar; he reveals to them that a strange duo was behind his condition and that they were last seen moving in the direction of Miranda.
Sabin rejoins you while Locke goes to check on the people of Narshe.
Journeying back south, they find the Opera to be in trouble once more and are called upon to aid it.
(Because I couldn't resist including another one of these.)
Eventually they reach Miranda; where they encounter a man and woman with the strength of Espers in human form who take you captive and hold you hostage in the ruins of the Tower of Fanatics.
By this time, Fayn has begun to recall his past and reveals to you that he is one of the three primordial Espers who were locked in the stone statues that gave Kefka his abilities. After the mad clown died; they were restored.
Long ago, the three had begun to fight over the fate of humanity with the other two deciding to destroy mankind while Fayn opposed them.
After they were freed, the others (Adrammelech and Mateus) stripped him of his powers before he could get away.
While they are waiting, Locke sneaks into the facility and sets them free.