Act I

An historian gives a brief overview of medieval  England. In an apparent (and deliberate) miscommunication between the actors and the narrator, an idyllic Scandanavian village appears, with gaily dressed Finnish villagers singing and dancing to the "Fisch Schlapping Song." The Historian returns, irritated, and tells the frolicking Finns that he was talking about England, not Finland. The villagers disperse and 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 large Bibles. King Arthur travels the land with his servant Patsy, who follows him around banging two coconuts shells together to make the sound of horses hooves as Arthur "rides" before him, trying to recruit Knight of The Round Table to join him in Camelot ("King Arthur's Song"). He encounters a pair of sentries who are more interested in debating whether two swallows could successfully carry a coconut than in listening to the king.

Robin, a collector of plague victims, and Lance, a large, handsome and incredibly violent man, meet as Lance attempts to dispose of the sickly Not Dead Fred ("He Is Not Dead Yet"). They agree to become Knights of the Round Table together, Lance for the fighting, and Robin for the singing and the dancing.

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, the sword given only to the man fit to rule England. 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 and her Laker Girls appear to turn Dennis into a knight ("Come With Me"). Cheered on by the girls ("Laker Girls Cheer"), the Lady of the Lake turns Dennis into Sit Galahad and together, they sing a generic Broadway love song ("The Song That Goes Like This"), complete with chandelier. They are joined by Sir Robin and Sir Lancelot, and together with Sir Bevedere and Sir Not-Appearing-In-This-Show (a knight resembling Don Quixote, who promptly apologizes and leaves), they make up the Knights of the Round Table ("All for One").

The five knights gather in Camelot, a deliberately anachronistic place resembling Las Vegas's Camelot-inspired Excalibur resort, complete with showgirls, oversized dice and the Lady of the Lake headlining the Castle in full Cher get-up ("Knights of the Round Table"/"The Song That Goes Like This (Reprise)"). In the midst of their revelry, they are contacted by God (a recording voiced by John Cleese of the original Monty Python troupe) who tells them to locate the Holy Grail. Urged on by the Lady of the Lake ("Find Your Grail"), the Knights set off. They travel throughout the land until they reach a castle, only to be viciously taunted by lewd French soldiers. They attempt to 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 should have hidden inside it. Defeated, they leave in a hurry when the French begin taunting them again, sending cancan dancers after them and throwing barnyard animals including cows at them ("Run Away!").

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 terrifying but silly Knights who say Ni who demand a shrubbery. King Arthur despairs of finding one, but Patsy cheers him up ("Always Look on the Bright Side of Life") and they find a shrubbery shortly after.

Sir Robin, after wandering the forest for some time with his minstrels ("Brave Sir Robin"), encounters The Black Knight, who scares him off, but King Arthur, who happens on the scene, more or less defeats him by cutting off both his arms and legs, impaling his still-alive torso on a door, and leaving to give the Knights their shrubbery. The Knights accept it, but next demand that King Arthur put on a musical and bring it to Broadway (in the United Kingdom, this became a West End musical; on the tour, they must put on a "Broadway musical", implying that it need only be Broadway-style, "but not an Andrew Lloyd Webber". The mere mention of his name causes everyone to cover their ears and scream in pain.). Sir Robin, who has found Arthur by this point, insists that it would be impossible for them to accomplish this next task, since you need Jews for a successful Broadway (or West End) musical ("You Won't Succeed on Broadway"), and proves his point in a wild production number filled with Fiddler on the Roof parodies, including a bottle dance like the one in Fiddler on the Roof, with Grails instead of bottles. King Arthur and Patsy promptly set off in search of Jews.

While the Lady of the Lake laments her lack of stage time ("Diva's Lament - Whatever Happened to My Part?"), Sir Lancelot receives a letter from what he assumes is a young damsel in distress. He is very surprised to find that the "damsel" is actually an embarrassingly unattractive, effeminate young man named Prince Herbert ("Where Are You?"/"Here Are You") whose overbearing, music-hating father, the King of Swamp Castle, is forcing him into an arranged marriage. As Herbert is asking Lancelot to help him escape, the King of Swamp Castle cuts the rope that he is using to climb out of the window, and Herbert falls to his death. Lancelot is a bit puzzled at the king's actions, but it is revealed that Herbert was saved at the last minute by Lancelot's sidekick, Concord. The King asks his son how he was saved, exactly, to which Herbert replies happily with a song. But the king charges at his son with a spear, preparing to kill him. Lancelot steps in to save him, then gives a tearful, heartfelt speech about sensitivity to the king on Herbert's behalf, and Lancelot is outed as a homosexual in the process, an announcement celebrated in a wild disco number ("His Name is Lancelot").

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 ("I'm All Alone"). The Lady of the Lake appears and tells Arthur that he and the Knights have been in a Broadway musical all along. Patsy also reveals he is half Jewish, but didn't want to say anything to Arthur because "that's not really the sort of thing you say to a heavily-armed Christian." 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 ("Twice In Every Show").

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. (The letters vary from show to show, but in the Broadway production and on the tour it is either A101, B101, C101 or D101. In the West End Production a word is revealed - DONE, CONE or BONE, referring to D1, C1 and B1 respectively.) 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". A large hand points to the audience and Arthur realizes that the letters and numbers refer to a seat number in the audience. The grail is "found" (with some sleight of hand) under the seat and the person sitting in the seat is rewarded with a small trophy and a polaroid photo. ("The Holy Grail"). Arthur marries the Lady of the Lake, who reveals that her name is Guinevere; Lancelot marries Herbert (who finally has a chance to sing); and Sir Robin decides to pursue a career in musical theatre ("Act 2 Finale/Always Look on the Bright Side of Life (Company Bow)").