It occurred to Ed Solomon and Chris Matheson as they worked on their idea that if other people thought their script was as funny as they thought it was, there might actually be a chance of selling it.  They gave the script to Ed’s agent who, after reading it, didn’t think it was something they could sell.  Chris gave the script to producer Stephen Deutsch (Somewhere in Time), who was a friend of his father (noted writer Richard Matheson).  Stephen then passed it on to Robert Cort, who had just started working for Interscope.  Interscope decided to option the script and Ed and Chris were paid to rewrite it.  Shortly after that, the buzz about the script somehow started.  It has been said that at one point Excellent Adventure was the mostly widely read script in Hollywood.  Warner Bros. expressed interest and Ed and Chris did several rewrites for them over a course of one year, attempting to tailor the script to the studio’s demands.  For instance, the idea of the time-traveling van was something Warners did not want because it was too similar to Back to the Future . . . Ed and Chris both preferred the van because Rufus would play music and Bill and Ted would ask who the band was, like the eventually scene in the future in the final movie.  Ed Solomon recounts, "We did a series of rewrites, continuously making the script worse, in my opinion.  We didn’t know any better - it was our first deal.  They kept saying, ‘This is a summer teen movie comedy which will only appeal to kids, so we have to emphasize that.’"  Warner Bros eventually passed on the film, citing their opinion that the teen-comedy genre was dead.

At the time, director Stephen Herek was enjoying notoriety from directing the dark comedy horror film Critters, which did well at the box-office, and he was being considered for other comedy horror films.  About the only script which he was excited about was Excellent Adventure.  "Warner Brothers were developing the project at this stage.  They initially approached me because they thought I could make it on the cheap.  After reading the script I realized it would be impossible to make a picture of any quality for less than a medium budget and that’s where the difficulties began.  It was mid-1986 when they finally decided to drop the project altogether.  Regarding Warners' opinion about teen movies, he explained, "I was familiar with the sort of characters Bill and Ted were.  I knew where they were coming from.  My brothers were archetypal and I even roomed with a similar couple.  But no-one believed they existed!  They couldn’t see the vast audience for the completed film.  I kept telling people to walk through the country’s shopping malls and see the characters first hand with the dialogue rap they have - ‘No way, Hey, dude, Way to go’.  I did this research and knew the script was spot on.  Everyone else felt the film would be of limited interest.  Six months later Dino De Laurentiis’s DEG company picked up the option and we finally entered pre-production."

They finally had a production company which would see the movie through its filming.  Chris recalled that at their one and only meeting with Dino De Laurentiis himself he kept wanting to know why it the story had to be set in San Dimas.  Ed and Chris explain that when they used to drive out to Las Vegas they would go through San Dimas.  To them it was in the middle of nowhere.  As Ed explained, "It wasn’t a beach town, it wasn’t a valley town, east of Los Angeles.  It was kind of nondescript."  Initially, Ed noted, one of them (Bill or Ted) was from San Dimas and the other was from San Gabriel.  People were still nervous about the time-traveling van being too much like Back to the Future and a change was needed.  The idea for the phone booth was suggested by director Stephen Herek, who was looking for something that would provide the exciting visual nature of a roller coaster ride.  Both Ed and Chris really liked Stephen, who told them that when he first started reading the script he put it down, put Van Halen on the stereo, and read it while listening to rock music.

Literally hundreds of kids auditioned for the roles of Bill and Ted.  Ed and Chris didn’t meet Alex and Keanu when they were cast but they did see their audition tapes.  At that time Alex was playing Ted and Keanu was playing Bill.  Ed and Chris felt it would be better if their roles were switched (Alex and Keanu have said they also wanted to swap roles early in the process).  The writers didn’t come face to face with Alex and Keanu until it was time to film in Phoenix, Arizona, and they went across the street to a McDonald’s to get something to eat and Alex and Keanu walked in.  Ed and Chris both reacted with, "Those guys should be Bill & Ted!"  Later, when they saw them on the set they realized they had seen their Bill and Ted in the flesh.  As director Stephen Herek, who agreed that casting the right actors in the roles of Bill and Ted was pivotal, remembered, "We saw hundreds of guys at extensive casting calls and zeroed it down to twenty-four finalists.  Then we spent an entire day mixing and matching couples to see if any chemistry sparked.  Keanu Reeves and Alex Winter had never met each other until that day, but we could tell immediately they were exactly right."

Producer Scott Kroopf also knew the casting was essential . . . the actors playing Bill & Ted had to have a certain chemistry or the movie wasn’t going to work.  He recalled that during the audition process, Alex and Keanu would be sitting in conversation in the outer room, then one or the other would go in and audition with someone else but that they would always come together again to talk between auditions.  As Keanu recalled for a teen magazine, "When we auditioned in the very, very beginning, Alex was the second person I read with.  And it was great, because I was sort of in a weird mood and so we went in and it was like, 'Whoa!  Check this out.'  It was a lot of fun."  However, casting Alex and Keanu caused the writers to make a slight modification in the characters, which were conceptualized as unpopular nerd-geeks.  As Ed Solomon explained, "Bill and Ted were conceived in our minds as these fourteen-year-old skinny guys, with low-rider bellbottoms and heavy metal t-shirts.  We actually had a scene that was even shot, with Bill and Ted walking past a group of popular kids who hate them.  But once you cast Alex and Keanu, who look like pretty cool guys, that was hard to believe."  After seeing Keanu audition for the movie, Stephen Herek knew in his mind that that was Ted, no matter who else he saw for the part.

Alex pointed out that while the script looked deceptively simple, it was actually very well written and gave him the opportunity to be able to say these really ornate lines.  He also explained how the appeal of the film for many is the willingness of Bill and Ted to be more childlike and act like kids as opposed to growing up and taking on adult responsibilities just yet.  He recalled that he and Keanu had become friends during the course of the audition process and when they had been cast they showed up and were told they were going to be playing the opposite roles they had done in the auditions: that Alex would be Bill and Keanu would be Ted.  Alex was thrilled to have the opportunity to work with a brilliant wordsmith comedian like George Carlin and recounts that they had a great time with him.  Alex credits Stephen Herek with keeping the project in line with his vision of a jovial, genuine, sincere and fun picture.

Casting the rest of the movie turned out to be quite a hip and esoteric affair.  Stephen Herek was determined to keep the cast quirky and interesting.  "I purposely wanted the ‘Hey, isn’t that . . . ‘ response," Herek explained, "Obviously stars like Madonna would have tipped the balance and detracted from the story.  Originally I wanted ZZ Top to be The Three Most Important People, but dealing with rock stars is always a huge problem.  My main concern was to keep the story in focus at all times."  Producer Scott Kroopf recalled how he had gone to a Comic Relief concert and saw George Carlin performing.  Having not seen him for fifteen years he had forgotten how amazing Carlin was.  Everyone agreed that casting George Carlin as Rufus was a big advantage for the production.

Stephen also referred to what he called the "puppy factor" in describing Bill and Ted, and especially Ted, should be like big Labrador Retrivers who just bounce along and love life, and in directing them would say, "There’s not enough puppy factor," to get them to make things even bigger and happier and bouncier. Ed and Chris had actually envisioned a darker version, more in line with the Monty Python films.

The script had undergone several rewrites, a production company had been found, and the casting was completed.  It was now time to make a movie!


Article Sources: 

Bill & Ted's Most Excellent Collection - Non-Bogus Disc: In Conversation with Screenwriters Chris Matheson & Ed Solomon
Bill & Ted's Most Excellent Collection - Non-Bogus Disc: The Most Triumphant "Making-of" Documentary
Cinefantastique, August 1991 - Writers Chris Matheson and Ed Solomon on the birth of a phenomenon
Starburst - May 1990