Butera is frequently regarded as a crossover artist who performed with equal ease in both R&B and the post-big band pop style of jazz that permeated the early Vegas nightclub scene.

Butera's professional career blossomed early, beginning with a stint in big band drummer Ray McKinley's orchestra directly after high school.

Butera was named one of America's top upcoming jazzmen by Look magazine when he was only eighteen years old, and, by his early twenties, he had landed positions in the orchestras of Tommy Dorsey, Joe Reichman, and Paul Gayten.

[2] As the big band era wound down and heavy touring became less common among jazz musicians, Butera re-settled in New Orleans, where he played regularly at the 500 Club for four years.

During that time, he performed with Louis Prima and/or Keely Smith on such Prima-associated songs as "That Old Black Magic", "Just a Gigolo/I Ain't Got Nobody," "Come on-a My House," and "I Wan'na Be Like You" (from Disney's The Jungle Book).

The arrangement he made with Prima of "Just a Gigolo/I Ain't Got Nobody" has been covered by David Lee Roth, Los Lobos, Brian Setzer, The Village People, and Big Bad Voodoo Daddy.

[7] Butera's advice for the host, Space Ghost's evil twin brother Chad Ghostal, on getting "chicks, like a fox [insert purr]" is "Well, first a little music, a little jive talk.

When he sang part of "Just a Gigolo," Chad, Zorak, and Moltar found it familiar and Butera began to tell how David Lee Roth stole the song from him.