The game takes place almost entirely in a fictional kingdom called the Land of the Green Isles. The kingdom comprises several islands, and is described as being largely isolated from the outside world. The player can travel between different islands after obtaining a magic map.
The center of the kingdom is the Isle of the Crown, which has an Arabian Nights theme. The Isle of Wonder is inspired by Alice in Wonderland, and the Isle of the Sacred Mountain is inspired by Classical mythology. The Isle of the Beast is heavily forested and scattered with magical barriers. There also are additional hidden areas. One of these is inhabited by a tribe of druids, while another gives the player the option to confront Death.
The game's opening cutscene shows Prince Alexander haunted by his memories of Princess Cassima, who he met at the end of King's Quest V when they were both rescued from the wizard Mordack. After seeing a vision of Cassima in the magical mirror that his father acquired in the first King's Quest, he sails to find her. At the beginning of the game he is shipwrecked on the shore of the Isle of the Crown, where he learns that the vizier Abdul Alhazred (named after the author of the fictional Necronomicon) has assumed control in Cassima's absence, and plans to force her marry him. Alexander must explore the Land of the Green Isles in order to find and learn what he needs to rescue Cassima from the vizier.