The 'plot' is introduced by the historian, who gives an overview of the setting: medieval England. Naturally, the cast goes on to sing a song about Finland (also using the opportunity to perform the famous Fish-Slapping Dance). After this misunderstanding is cleared up, King Arthur and his servant Patsy arrive on the scene in search of knights for the round table. They promptly get into an argument about swallows with some guards.
Later, Arthur and Patsy find Robin, a plague victim collector, and Lancelot (who is trying to dispose of a man who turns out to be "Not Dead Yet") and convince them to join the quest. Next, Arthur comes across a politically active peasant named Dennis, who denies Arthur's right to rule. To change his mind, Arthur summons the Lady of the Lake, who convinces Dennis to become Sir Galahad. Somewhere, they also pick up Sir Bedevere (and the aptly-named Sir Not-Appearing-In-This-Show).
After arriving in a Las Vegas-inspired Camelot, the knights are contacted by the voice of God (a recording of John Cleese or in the touring production, Eric Idle) who wants them to search for the Holy Grail. They set out immediately, but are defeated by the incessant taunting of their French enemies. The knights become separated and Arthur ends up in a "dark and very expensive forest", where he is "All Alone" (sort of). He then meets the Knights Who Say Ni, for which he and Patsy go off to find a shrubbery.
Meanwhile, Sir Robin is being annoyed by his minstrels when he happens upon the Black Knight. Robin is terrified, but Arthur bursts on the scene and defeats the Black Knight more or less how one would expect. The KWSN want their shrubbery to be in a Broadway musical. Robin tells Arthur he cannot have a good musical without Jews, so he and Patsy go off to look for some.
Meanwhile, the Lady of the Lake complains about her lack of stage time. Sir Lancelot storms a castle to save who he believes is a princess in distress. Naturally, it turns out to be Prince Herbert, a musically-inclined lad with a music-hating father. And everyone thinks Lancelot is gay.
When Patsy reveals he is Jewish, Arthur can resume his quest for the Holy Grail. Reunited with the others, Arthur encounters Tim the Enchanter, who warns them about an evil rabbit. They defeat the rabbit with Holy Hand Grenade of Antioch and proceed to find the Holy Grail under the seat of an audience member. Arthur marries the Lady of the Lake aka Guinevere, Prince Herbert finally gets to sing and marries Sir Lancelot, and Sir Robin decides to go into musical theater.
