Act I: The play begins with a historian giving a brief overview of medieval England. The pastoral forest is immediately replaced by a dreary, dark village with penitent monks in hooded robes chanting Latin prayers and hitting themselves in the face with wooden boards. King Arthur travels the land with his servant Patsy, trying to recruit Knights to join him in Camelot and his quest for the Holy Grail. Sir Robin and Sir Lancelot meet as they attempt to dispose of the sickly Not Dead Fred. They agree to become Knights of the Round Table together.

Meanwhile, Arthur attempts to convince a peasant named Dennis Galahad that he (Arthur) is king of England because the Lady of the Lake gave him Excalibur. However, Dennis and his mother, Mrs. Galahad, are political radicals and deny that any king who has not been elected by the people has any legitimate right to rule over them. To settle the issue, Arthur has the Lady of the Lake appear to turn Dennis into a knight. The Lady of the Lake turns Dennis into Sir Galahad. Together, with Sir Bedevere and Sir Not-Appearing-In-This-Show, they make up the Knights of the Round Table.

The five knights gather and in the midst of their revelry, they are contacted by God, who tells them to locate the Holy Grail. Urged on by the Lady of the Lake, the Knights set off. They are viciously taunted by lewd French soldiers at a castle and retaliate by sending them a large wooden rabbit in the style of the Trojan Horse; however, they realize after the fact that it was not as simple as leaving the rabbit and walking away - they were supposed to be inside of it.

Act II: Sir Robin and his minstrels follow King Arthur and Patsy into a "dark and very expensive forest" where they are separated. King Arthur meets the Knights who say Ni, who demand a shrubbery. King Arthur despairs of finding one, but Patsy cheers him up and they find a shrubbery shortly after. The Knights accept it, but next demand that King Arthur put on a musical and bring it to Broadway. The Black Knight appears but King Arthur more or less defeats him by cutting off both his arms and legs. Sir Robin, after wandering the forest for some time, finds King Arthur and insists that it would be impossible for them to accomplish this next task. King Arthur and Patsy promptly set off in search of Jews.

While the Lady of the Lake laments her lack of stage time, Sir Lancelot receives a letter from what he assumes is a young damsel in distress. He is a little surprised to find that the damsel is actually an effeminate young man named Herbert whose overbearing, music-hating father, the king, is forcing him into an arranged marriage. Lancelot advocates for Herbert after the king returns, and Lancelot is outed as a homosexual in the process. King Arthur begins to give up hope of ever putting on the Broadway musical and laments that he is alone, even though Patsy has been with him the entire time. The Lady of the Lake appears and tells Arthur that he and the Knights have been in a Broadway musical all along. All that's left is for King Arthur to find the Grail and marry someone.

After picking up on some not-too-subtle hints, Arthur decides to marry the Lady of the Lake after he finds the Grail. Reunited with his Knights, Arthur meets Tim the Enchanter who warns them of the danger of an evil rabbit. When the rabbit bites a knight's head off, Arthur uses the Holy Hand Grenade of Antioch against it, knocking down a nearby hill and revealing that the "evil rabbit" was actually a puppet controlled by a surprised puppeteer. A large stone block showing a combination of letters and numbers is also revealed.

After pondering the final clue, Arthur admits that they're "a bit stumped with the clue thing" and asks God to "give them a hand". The grail is "found"; Arthur marries the Lady of the Lake; Lancelot marries Herbert; and Sir Robin decides to pursue a career in musical theatre.