The show opens with the Star Trek theme song.  Captain Kirk and Captain Picard beam down to Gotham City (circa 1880) to look for the time traveling phone booth.  Kirk is overacting as usual, which brings some snide remarks from Picard (Picard comments that at times Kirk acts like a "real #2").  The phone booth arrives with Bill and Ted and the introduce themselves.  They say they received a call from a big record company who asked them to come there to make a deal with Wyld Stallyns.  Kirk and Picard tell them theyíve been duped, that the Borg are trying to get their hands on the booth to use it to travel through time.

The Borg Queen and a Klingon appear.  The Klingon comments that he sees Captain Kirk is still the Captain of the U.S.S. Rogaine, then makes a "Wax on, wax off" joke about Picardís head.  Kirk and Picard try to use their phasers against them but the Klingon explains that their weapons wonít work since they havenít been invented yet (the Klingon talks a lot like Doc Brown from Back to the Future at times).

The Klingon and Borg threaten the captains and Bill and Ted with guns, when suddenly Ripley from the Alien movies, the Men in Black and the Terminator (on his motorcycle) arrive.  A gunfight ensues, ending with the Klingon and Borg Queen escaping in the phone booth.

Bill and Ted greet the heroes, but when Ted called Ripley a dudette she punches him out.  Bill and Kirk get into an argument, Kirk saying he knows more about time travel . . . that heís even transported whales through time, to which Bill jokes that it looks like heís transporting one right now and patting Kirkís stomach!  Bill calls back the phone booth.

The Klingon and Borg Queen return in the booth, bringing with them Darth Vader, Poison Ivy from Batman (who comes down on a vine), and Mr. Freeze from Batman, who enters accompanied by the music Snow Miser from The Year Without a Santa Claus.  The Borg Queen fights Picard and the Klingon fights with Kirk.  Both Kirk and Picard are defeated and forced into the phone booth which takes off.

Bill is threatened by Darth Vader.  Vader tells Bill "The Force is with you but you are not a Wyld Stallyn yet!"  Bill and Vader fight with light sabers . . . finally he is able to position Vader on a garbage shoot (the gallows) and Ted flushes him down into the garbage.  The masked villain from Scream suddenly appears and starts after Bill and Ted but Mr. Freeze also appears and goes after them.  The Terminator interferes and he and Mr. Freeze fight, their blows not affecting each other at all.  Mr. Freeze headbutts the Terminator and when the Terminator lunges at him he misses and falls into the well, which Mr. Freeze freezes.  He then turns his freeze ray on Bill and Ted, telling them to "Chill!" and they freeze into snowmen.

Bill and Ted have called Batman using the Bat Signal before they are frozen, and Batman, Robin and Batgirl arrive on ropes.  Batgirl calls the dudes "Bill and Ted-sicles" and carries them offstage, saying she knows how to "warm them up."  Robin fights with Poison Ivy and when she goes after him to "whip the bird boy into shape" the Men in Black blow her up in a building.  Batman fights Mr. Freeze and then takes on the Borg Queen on top of another building and the Men in Black eventually shoot her down.

Bill and Ted reappear, having been defrosted by Batgirl, and announce itís time to jam.  They ask the Men in Black if they are not totally psyched, but the Men in Black are concerned about how they will get back to the future.  The Back to the Future theme starts and the DeLorean appears, only when the doors open the cast of Seinfeld get out!  Seinfeld comments that *this* is a show about nothing.  He then asks Cosmo Kramer how he managed to get them there and Kramer explains that he drove 88 miles and hour and zoom, they were there!

Bill and Ted assure everyone that they can fix the DeLorean and break into singing "Greased Lightning" from Grease with Kramer.  At the end of the song Billís cell phone rings and it is the villain from Scream, who appears from a building in his hood and mask . . . then he throws off the disguise to reveal it is Austin Powers!  Everyone dances to the Austin Powers theme, then the Men in Black interrupt and start performing their theme song.  Next Elaine from Seinfeld butts in and starts singing "Wannabe" by the Spice Girls.  She is joined in the song by the Borg Queen, Batgirl and Poison Ivy.

Finally Wyld Stallyns take center stage with Captain Kirk on lead as they perform "Smells Like Teen Spirit" by Nirvana.  At the very end Kramer blows up the set.

Many thanks to Michael for helping with the synopsis of this show!