The game begins at the gates of Narshe, with a party of a girl (unnamed at present but later revealed to be Terra), Biggs and Wedge. After a number of easy fights, they find themselves fighting a lightning whelk. They get past this obstacle by never attacking the shell, instead healing while they wait for it to reveal its head.
After this, they reach the Frozen Esper. A strange light emanates from the creature, causing Biggs and Wedge to vanish and the Magitek armour that Terra rode to explode.
Later, Terra awakens in a house. There, it is revealed that she remembers nothing apart from her name, due the slave crown on her head. When the town guard demands that she be handed over, Arvis sends her out through the mines to escape her pursuers.
Unfortunately, the town guard catches up to her, and she is about to be captured, but Locke, Mog and a group of Moogles are able to rescue her. Locke then joins her, recommending that she go with him to Figaro Castle.
When the pair of travelers reach Figaro, they meet Edgar, who tells them that Figaro is allied with the Empire, but he permits them to wander the Castle freely. Locke informs Terra that Figaro's alliance with the Gestahllian Empire is a front, and that Edgar is secretly working with the Returners, an organization devoted to overthrowing the Empire.
At this point Kefka arrives, asking about the whereabouts of "a girl", claiming that she is merely a small-time thief who stole something of value. Edgar claims not to be able to find her in his castle due to girls being as numerous as "the sands of the sea" in his palace. Kefka leaves with a vague threat, only to return later, setting the castle on fire.
Edgar, Locke and Terra leave Figaro on Chocobo-back, and Kefka is impressed by this bold (and apparently selfish) act by Edgar, but then Figaro Castle sinks into the sands, preventing Kefka from harming it or its inhabitants further. A pair of Magitek-armoured troops sent by Kefka to stop Terra & co. are soundly defeated by them and the party heads towards the town of South Figaro on their way to the headquarters of the Returner to see Banon, the leader.
While in South Figaro, they meet Shadow in the bar, who only says "Leave us. The dog eats strangers" at this time.
Near the summit of Mt. Koltz, they encounter a man named Vargas, who attacks them. Sabin (Edgar's brother and a trained martial artist) shows up and defeats him, then joins the group.
The party of four eventually arrives at the Returners' hideout. Banon encourages Terra to join, and when she eventually does, the organization starts to discuss its strategy for dealing with the Empire. The talks are cut short by the arrival of a soldier who informs them that South Figaro has been invaded by Imperial forces. Locke goes to South Figaro to attempt to slow down the invasion plans, while Banon takes Terra, Edgar and Sabin up the Lete River to Narshe to enlist their aid against the Empire.
Before they can reach shore at their destination, Ultros attacks them, but is defeated. In the ensuing confusion, Sabin is separated from the rest of the group.
At this point the story splits off into three branches.
Locke has had some success at his task, but feels the time is right for a getaway. However, on his way out, he rescues Celes, a disgraced Imperial General.