In November 1979 Cabaret Voltaire toured the United States, and became strongly interested in the rise of the Christian right and its use of television, especially the fund-raising broadcasts of TV evangelistEugene Scott. They compared this to the rise of Islamism, devoting a side to each strand of religious politics on their 1980 mini-album Three Mantras. Red Mecca was a culmination of this interest. According to Richard H. Kirk: "The whole Afghanistan situation was kicking off, Iran had the American hostages [...] we were taking notice [...] it's not called [Red Mecca] by coincidence. We weren't referencing the fucking Mecca Ballroom in Nottingham!"
Red Mecca was recorded at Western Works, Sheffield in May 1981.
AllMusic praised the album, writing "Unlike a fair portion of CV's studio output, Red Mecca features no failed experiments or anything that could be merely cast off as 'interesting'. It's a taught [sic], dense, horrific slab lacking a lull."