Originalmente, Alex Winter fez o teste para o papel de Ted e Keanu Reeves para o papel de Bill.
No filme, Bill e Ted afirmam que eles precisam de Edward Van Halen em sua banda para que ela fosse melhor. Depois do lançamento do filme, Van Halen brincou dizendo que se juntaria à banda deles se eles pedissem.
A cabine telefônica usada como máquina do tempo no filme foi doada a um prêmio da revista Nintendo Power, na época em que a franquia estava promovendo um novo jogo de Bill e Ted para NES (Nintendo Entertainment System).
No roteiro original, a máquina do tempo seria uma Van da Chevrolet, modelo 1969, mas os cineastas acharam que seria uma cópia de De Volta para o Futuro (1985), que utiliza uma DeLorean para viagens temporais. Então, eles mudaram para uma cabine telefônica (aparentemente desconhecendo o fato de que a série Doctor Who, de 1963 e também de 2005, utiliza uma cabine telefônica de polícia como uma máquina do tempo). Caso a ideia da van se mantivesse, Bill e Ted teriam pego mais figuras históricas do que na versão final do filme.
Na capa do VHS britânico, relançado em 1997, há uma foto de Bill e Ted usando ternos, de braços dados com as Princesas "gatinhas do passado" que aparecem no filme. Isso é claramente de uma cena deletada do baile de formatura do colégio, que deveria ter aparecido próxima do final do filme.
A música Play With Me, da banda Extreme faz parte da trilha sonora do filme. Pouco depois do lançamento do longa, Alex Winter, intérprete de Bill, dirigiu o videoclipe do hit Decadence Dance desta mesma banda.
Quando Napoleão, interpretado por Terry Camilleri, termina sua apresentação no tobogã, Ted olha o que ele está fazendo e diz "Acho que isso não vai funcionar". Se você olhar com cuidado os mapas, pode ver que Napoleão está na verdade diagramando a invasão francesa à Rússia, que historicamente foi sua maior derrota.
A cena em que Napoleão desliza pelos tobogãs em "Waterloo" foi filmada no Parque Aquático Golfland/Sunsplash em Mesa, no Arizona.
A cena de resgate de Bill e Ted, no qual seus camaradas fingem ser os carrascos e eles escapam em carruagens movidas à cavalo, inspira-se no modo em que D'Artagnan é resgatado em Os Três Mosqueteiros (1993), que também foi dirido por Stephen Herek.
A fotografia do filme foi completada em 1987, mas o lançamento foi adiado porque os financiadores oficiais do filme, De Laurentiis Entertainment Group, faliu. O filme estava fadado a ser distribuído somente na tv a cabo, até que a Nelson Entertainment comprou os direitos do longa em 1988, e então ele chegou aos cinemas em 1989.
Quando Bill lê a tarefa a Ted, ele diz: "Expressar para a classe como uma figura histórica importante de cada período veria o mundo de San Dimas, 1988". Seus lábios na realidade estão dizendo "San Dimas, 1987" e o número "1988" foi inserido depois por causa do atraso no lançamento do filme.
Napoleão se esbalda em um sundae napolitano na sorveteria Ziggy Pig que ele se refere como "La glacé". Mesmo que hajam similaridades entre o sorvete e seu nome, a sobremesa originou-se em Naples, na Itália. Historicamente, Napoleão Bonaparte de fato desenvolveu um apreço pelo doce quando chegou no país.
O prato "Ziggy Pig" na sorveteria é uma referência a um personagem da história em quadrinhos "Ziggy Pig and Silly Seal", publicada pela Timely Comics (atual Marvel Comics) nos anos 1940. Na época em que Bill & Ted - Uma Aventura Fantástica foi feito, esse personagem e sua imagem - que aparece no distintivo colocado no peito de Napoleão na cena da sorveteria - já eram de domínio público. O prêmio em si que Napoleão recebe foi baseado na faixa que poderia ser ganha na Franquia de Sorveterias Farrel, durante a competição de "Pig Trough", para quem comesse uma banana split de tamanho duplo. Os restaurantes Farrell foram uma enorme franquia nos anos 1970, mas poucos permaneceram no ano 1988.
O guitarrista americano Stevie Salas fornece o dedilhado do personagem Rufus durante a jam session (termo musical para indicar uma sessão de improviso) no fim do filme.
O filme começaria com Bill e Ted em um ato em pé (stand-up) no qual os personagens discutiriam eventos da atualidade sem saber sobre o que estavam falando. Originalmente, havia um terceiro personagem chamado Bob, mas o comediante que o interpretava perdeu o interesse depois de algumas atuações.
No esboço inicial do filme, Rufus era um estudante veterano de 28 anos que faz amizade com Bill e Ted. Havia também um personagem chamado John, o servo, que Bill e Ted pegavam na Inglaterra medieval.
No final original, Bill e Ted entregariam seu relatório de história em sala de aula, com todas as figuras históricas apresentando seus pontos de vista no quadro-negro.
Esta é uma de quatro produções nas quais Genghis Khan e Abraham Lincoln aparecem juntos como personagens, apesar de Lincoln ter nascido 582 anos após a morte de Khan. As outras foram no episódio da terceira temporada de Jornada nas Estrelas: The Savage Curtain (Por Trás da Cortina, em português), de 1969; na série de tv Clone High (2002) e no filme Uma Noite no Museu 2.
O discurso de Abraham Lincoln no final do filme foi uma paráfrase do Gettysburg Address, o famoso discurso que Lincoln fez durante a Guerra Civil Americana.
Durante a apresentação do relatório de história, Bill menciona que ele tem Complexo de Édipo. Esse é um termo usado primeiramente por Freud para descrever o desejo de um filho(a) de possuir o progenitor do sexo oposto. Isso faz referência ao confuso desejo sexual que Bill tem por sua madrasta, Missy.
A cena do shopping foi filmada no Metrocenter Mall em Phoenix, Arizona, em 1987. Alguns dos figurantes em cena eram crianças de um colégio local, Cortez, enquanto eles estavam no intervalo para o almoço.
A banda punk The Ataris escreveu uma música baseada no relatório do personagem Ox. A música é intitulada "San Dimas High School Football Rules!" (em tradução livre: O Futebol do High School de San Dimas arrasa!) mas não tem nada a ver com o filme.
As cenas externas da escola de Bill e Ted são do colégio Coronado High School em Scottsdale, Arizona. O impressionante mosaico é destaque da fachada do auditório da escola e foi projetado pelo professor de arte de lá, Sr. Gatti, e seus alunos no início dos anos 1960.
Na época, algumas das frases de efeito em alemão usadas no filme - por exemplo, "Volle Kanne, Hoschi" (em tradução livre: "É isso aí, cara") - se tornaram tão populares que foram adaptadas por muitas pessoas e usadas na linguagem popular.
A imagem da camiseta de Ted é capa do single de Van Halen "Why Can't This Be Love" que foi vendida durante a turnê 5150 de Van Halen e era comumente usada por fãs da banda no final dos anos 1980.
Pauly Shore e Josh Richman fizeram o teste para o papel de Ted.
Este é o primeiro de dois filmes sobre as aventuras de Bill e Ted, o segundo é Bill & Ted - Dois Loucos no Tempo (1991). Há rumores sobre fazer um terceiro filme. Os protagonistas Alex Winter e Keanu Reeves já disseram em entrevistas que adorariam voltar a interpretar Bill e Ted, respectivamente.