Paul Sanchez (vocals, guitar) had previously recorded as a solo artist before teaming up with Fred LeBlanc (vocals, drums). The pair formed the Backbeats, who were short-lived. After their breakup, Sanchez moved to New York, where he continued to perform solo. In 1988, he returned to New Orleans; LeBlanc, who had just finished playing with Dash Rip Rock, had Sanchez join his new band. The duo began jamming with Griffith (lead guitar, vocals), who had just left the Red Rockers, a new wave band who had a hit with "China." The trio played with a variety of bassists until 1993 when Rob Savoy, the former frontman for the Blue Runners, joined the band. The band released their first album, Mouthing Off, late in 1993 on the independent Viceroy Records. Two years later, they released It Means Escape on the Monkey Hill label.
By 1995, the group's following had grown large enough to earn attention from major labels. Cowboy Mouth decided to sign with MCA in early 1996, and they recorded their major-label debut, Are You With Me, with producer Michael Wanchic during Mardi Gras of that year.