The Longhorn Cheddar Cheeses are a group of cheeses who were meant to have performed "The Thunder Rolls" with Garth Brooks in episode 102 of Muppets Tonight. When Brooks arrives, he wants to do anything but his own songs, so the cheeses find themselves in particular conflict with The Barbershop Cactus Quartet who were also promised a spot with the country singer. However, Rizzo has placed the cheeses on a higher priority due to his special relationship with their food group.

Some members were formerly members of François Fromage and his Dancing Cheeses.

Other songs performed by the band, according to a vinyl record decorating a wall in PizzeRizzo, include "Bleu Moon", "What Cheese Doin Now", "Fromage in Low Places", and "I'll Treat You Cheddar."