Open-world before the term existed, Faery Tale from the beginning confronts the player with a vast land – equivalent to 17 thousand screens-worth of material – that can be explored in (nearly) any order one chooses, striding freely across open meadows, tundras, farmlands, dense and forbidding woods, desert, bogs, and volcanic wasteland. Punctuating the landscape are various buildings, caverns, or other indoor locations, sometimes named on the paper map accompanying the game. Showing the contours of the world and various sites scattered about it, the map is an essential tool and also serves as copyright protection, as when booting the game you're required to input three words from the rhyme wrapping around the map.

The immense charm of the game contributes greatly to the fun of exploration. Although the music consists of only half a dozen tracks, the game makes the most of them and of the Amiga's superior sound capabilities. Both the daytime and night-time themes are superb, and will be interrupted by a tense battle theme as enemies randomly spawn on the fringes on the map and pursue you.

If the player tires of hiking, it is possible to gain the ability to summon a sea turtle that will graciously permit the brother to ride on its back over the seas, reaching otherwise inaccessible locations. Later still, a magic lasso permits the taming of a giant swan, allowing the brother to literally “wing forth in flight” as the rhyme indicates. Logistics are present in the game, not only in a day-and-night cycle (magical green jewels provide short-lived light), but also in the need for food and sleep. Going too long without buying food from an inn results in starvation eating away at the brother's vitality, but going too long without sleep means the brother will move in a drunken fashion, unable to walk a straight line!