The Muppets performed two acts for the program, both taped during the first week of March in 1966. The first was what would become known as the "Music Hath Charms" sketch, which aired 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".
In the second, which was included 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.
The Muppets would return to the very stage where The Hollywood Palace originated in 2001 for The Muppet Show Live.