The Hollywood Palace was an ABC Saturday night TV show broadcast live from the El Capitan Theater (aka, ABC Palace Theater) during the 1960s.
The Muppets performed what would become known as the "Music Hath Charms" sketch on the March 19, 1966 show hosted by Robert Goulet. Also in that episode, Nancy Sinatra sang "These Boots Were Made for Walking" and "As Tears Go By", and Chita Rivera performed "My Home Is In My Shoes".
On the April 30, 1966 show, hosted by Fred Astaire, Kermit performed the "Inchworm" sketch. That episode also included performances by Louis Nye, Herb Alpert & the Tijuana Brass, and lion tamer John Zerbini.