The band first appeared in the middle of 1979 performing under a number of names including the Tomcats, the Teds, and Bryan and the Tom Cats. According to Brian Setzer, the band changed names to fool club owners (who would not hire the same band for consecutive nights), but kept the "Cats" moniker in their various names so the audience would know they were the same band. Setzer joined up with Phantom, and they soon added Phantom's schoolmate and friend, Lee Rocker. The three later realized they were from the same neighborhood and enjoyed punk and rockabilly music. Since 1983, they have used only "Stray Cats" as their name. The band name "Stray Cats" had already earlier appeared in the 1973 rock 'n' roll film "That'll Be the Day" and its 1974 sequel "Stardust". They also went to many concerts and enjoyed the punk scene. They met the Clash and they used to see Siouxsie and the Banshees, and also Charlie Harper and the UK Subs.