Based on the movie.
You control Bill & Ted- Rufus, a time travelling "dude" from the future, gives you use of a time-travelling telephone booth. Use the phone booth to go back in time to many different eras, collect items, and get historical "dudes" to follow you. Some "dudes" won't come unless you can bribe them with the right object. You must get them to follow you back to modern times so you can pass a history report and keep your band, the "Wyld Stallyns" together.
At the end of the game, you are graded based on time elapsed, and "dudes" accumulated.
The credits on the back of the box are in Bill-and-Ted-speak, giving recognitions such as "bodacious graphics", "triumphant sound", and "excellent programming". Also the game is rated "ME" (Most Excellent).