Az Ifjúsági Magazin 1967 végén közölt riportot a Decca zenekarról, amelynek vezetője, Winkelmayer József egy új név kiválasztásában kérte az olvasók segítségét. A beérkezett javaslatok egyike sem nyerte el az együttes tagjainak tetszését, akiknek végül Keszler Pál, az Országos Rendező Iroda vezetője javasolta, hogy vegyék fel az Olympia nevet, hiszen 1968 az olimpia éve. 1968 januárjától ezért a Decca helyett először rendszertelenül, majd egy idő után következetesen az Olympia nevet kezdte használni a Winkelmayer József pozan, Horváth Charlie ének és trombita, Kovacsics Öcsi gitár, Bálint István dob és Fábry Zoltán basszusgitár felállású együttes. Bálint nem maradt túl hosszú ideig a csapatban, még ebben az évben Szentgyörgyi András „Picike” váltotta őt a doboknál.
Az Olympia minden csütörtökön és vasárnap a Kőbányai Ifjúsági Házban lépett fel. A Kinks, Donovan, a Spencer Davis Group, a Beatles, Alan Price, a Spooky Tooth, a Small Faces, a Bus Stop, Tom Jones és Joe Cocker dalainak feldolgozásait játszották, illetve kezdetben Hurricans-, Ventures- és Shadows-szerzemények is szerepeltek a repertoárjukon.