Bill y Ted tienen un problema: cuando comprueban que van a suspender en su clase de historia, y, por lo tanto, van a repetir de año escolar, Ted será enviado a una academia militar y la banda Wyld Stallyns (los sementales salvajes) de los dos adolescentes tendría que disolverse.
Un viajero en el tiempo del futuro llamado Rufus llega a San Dimas (California) con su máquina del tiempo con la forma de una cabina de teléfono para salvar a la banda de Bill y Ted y con ello salvaguardar el progreso del futuro.
Así, Bill y Ted comienzan a viajar en el tiempo en esta cabina y conocen a Sócrates, Napoleón, Ludwig van Beethoven, Juana de Arco, Genghis Khan, Sigmund Freud, Billy the Kid y Abraham Lincoln en la década de 1980, donde las figuras históricas hacen que Bill y Ted se metan en un gran lío siendo arrestados y detenidos en la comisaría.
Bill y Ted consiguen liberar a los personajes históricos.
Su presentación escolar será un gran éxito, por lo que pasan el examen y pueden seguir tocando juntos y convertirse en una exitosa banda que marcaría la historia mundial para siempre.