The show opens with a brief Prologue as the Vizier's daughter Sheherazade tells her younger sister Dinarzade, a bed-time story on the eve of King Shahryar's wedding. All the population celebrates The King's Wedding. Everyone is happy and secure until the King discovers he has been betrayed by his wife and has her and her lover executed. He vows he will never again let a woman take advantage of him and announces he will marry a new wife each day and have her executed the following morning. After Many Weddings, Sheherazade volunteers to marry the King and bring an end to the deaths.

Sheherazade persuades her distraught father to arrange the marriage and explains to Dinarzade how she plans to save her own and the kingdom's other women's lives - by telling stories. Sheherazade's Wedding is a more sombre affair with everyone in the kingdom expecting her to become yet another victim. The King and Sheherazade process to his chamber for her wedding night.

On The First Morning after the wedding, Sheherazade persuades her husband to allow her to tell Dinarzade a final story, he decides to listen as well. She launches into the story of Ali Baba and the Forty Thieves (Part One). The story comes to life and the King becomes wrapped up in the fortunes of Ali Baba, his brother and the thieves but is angered Later the First Morning when Sheherazade stops half way through the story saying it is time for her execution.

With nobody able to tell him the end of the story, Shahryar decides to let his wife live another day so that she can finish the story later that night. Her strategy has worked. Later that day Sheherazade tells the story of Ali Baba and the Forty Thieves (Part Two) and speaks through the night until The Next Morning when it is time for the Swordsman to do his work.

Asked by Dinarzade if she is afraid of dying, Sheherazade replies saying she is no more afraid than the fisherman who found a genie in a bottle in one of their favourite stories. The King demands to hear the story and announces that his wife will remain alive another day in order to tell it. She tells the story of The Fisherman and the Genie, delighting the King. After the story Sheherazade Sleeps and the Citizens show their concern for her future, while the King decides that he will not let the situation continue. The act ends with Shahryar telling the sleeping Sheherazade that it is time to end her life.

In Act Two, King Shahryar explains to the Vizier that he has become fond of Sheherazade but is afraid her love for him will go the same way as his first wife. Because of that, the King has decided she must die. And so Sheherazade Faces Execution. As she walks towards her fate, she reminds her sister of another story which at the last moment the King demands to hear. Sheherazade is reprieved once more. Needless to say everybody except the Swordsman is delighted. Later that day Sheherazade tells the story of The Ass and His Ass. At the end of the story an amused King talks of future stories but adds a reminder that he is still in control of his wife's destiny.

The Citizens explain how the stories continue for more than a year. On one night, Sheherazade and Dinarzade tell him the story of The Little Beggar and hint that the next story will be that of Sinbad the Sailor. The King looks forward to Sinbad; his feelings for Sheherazade have grown to love.

Sheherazade has been telling stories to her husband for 1000 nights. Her execution is barely mentioned. On the 1001st night she tells the King she has run dry of stories and reminds him of his vow that the end of the stories would mean the end of her life. He is distraught until she says she has one more story but that she does not know the end of it. He insists she tell the story and so she begins Sheherazade's Story. It soon becomes clear she is telling him his own history as she talks of how a young girl loved the King despite his becoming a tyrant, killing wives day after day. He angrily interrupts but she tells him it is her own story and continues until she reveals that she is expecting the King's child. King Shahryar is delighted, proclaims that the death sentence upon his wife is lifted and, in the Finale, they sing of their love for each other and are joined by the Citizens who sing the main theme, Arabian Nights.