The song was first recorded for Mingus' 1959 album, Mingus Ah Um. Columbia refused to allow the lyrics to the song to be included, and so the song was recorded as an instrumental on the album. It was not until October 20, 1960 that the song was recorded with lyrics, for the album Charles Mingus Presents Charles Mingus, which was released on the more independent Candid label. Due to contractual issues with Columbia, the song could not be released as "Fables of Faubus", and so the Candid version was titled "Original Faubus Fables". The personnel for the Candid recording were Charles Mingus (bass, vocals), Dannie Richmond (drums, vocals), Eric Dolphy (alto saxophone), and Ted Curson (trumpet). The vocals featured a call-and-response between Mingus and Richmond. Critic Don Heckman commented of the unedited "Original Faubus Fables" in a 1962 review that it was "a classic Negro put-down in which satire becomes a deadly rapier-thrust. Faubus emerges in a glare of ridicule as a mock villain whom no-one really takes seriously. This kind of commentary, brimful of feeling, bitingly direct and harshly satiric, appears far too rarely in jazz."
The song, either with or without lyrics, was one of the compositions which Mingus returned to most often, both on record and in concert.