As the story opens, you and your companions are celebrating in triumph. The caravan you've been guarding has just completed its dangerous passage to the trading town of Yartar. But the realms are full of danger and there is tension in the air. Great armies are on the move, and the relative peace of recent times will soon be shattered. Your party becomes a problem to the evil forces whose plans lie behind the current troubles. Only by the swiftness of your sword--on land and water--will you live to save the region from certain destruction.

The game revolves around a standard (for Gold Box adventures) party of six adventurers who inadvertently get caught up in a plot by the Zhentarim to conquer the entire Frontier area.

The storyline, in rough terms, follows:

The party starts off in Yartar, having just escorted a caravan from the dwarven stronghold Citadel Adbar (ruled by the dwarf king Harbromm). At the tavern, while the party is enjoying the feast and spirits, something is slipped into their food that causes them to pass out, and they are robbed of all gold and gear, especially the magic longsword that one member used to slay a griffon at Longsaddle. Fortunately, each character keeps a purse of coins under their pillow so they can buy armour and weapons.

Through rescuing the NPC Krevish, the party being hired by the Kraken in Yartar to assassinate a cleric of Bane at Nesme, only to discover that this evil priest was the only individual standing in the way of the conquest.

Rescuing the magic user Amelior Amanitas from Everlund, an eccentric and somewhat absent-minded wizard who explains how to stop the Zhentarim. Returning to Yartar, the party is captured and imprisoned in a Kraken base below the city. There, the magic longsword stolen at the start is recovered but the party has to fight four giant squid in a huge tank before escaping.

Finding four magical statues scattered across the frontier before the Zhentarim, led by a General Vaalgamon, gets to them.

Traveling to the dead city of Ascore to end the Zhentarim plot.

Basically, Zhentil Keep plans to use these magical statues to open a way through an otherwise-unpassable desert for their armies. If successful, the party is hailed as the "Heroes of Ascore," which is carried over into the sequel.