This was the band's first album not recorded with original guitaristBrett Gurewitz (since the 1985 EP Back to the Known) and is their first release with Brian Baker, who replaced him during the Stranger Than Fiction tour. It was also the first album since How Could Hell Be Any Worse? that the band recorded as a group.[clarification needed] Part of the reason for this was financial, but frontman Greg Graffin also wanted to foster a sense of unity following Gurewitz's jarring departure. This was also the first album with which Graffin solicited the opinions of other band members before recording. Graffin said that collaboration significantly improved the sound and quality of the album.
Some songs on the album are considered fan favorites, such as, "Them And Us", "A Walk", "Punk Rock Song", "Spirit Shine", Ten In 2010", "Come Join Us", and "Cease".
Although not as successful as Stranger Than Fiction, The Gray Race achieved modest success when MTV ran a commercial for the album during its release. The album was re-released by Epitaph Records on September 15, 2008.
The Gray Race was released on February 27, 1996 and peaked at #56 on the Billboard 200 album chart. It spawned the moderately successful single "A Walk" in the United States. In Europe, the album also reached the German charts at #6 as well as earn the group a gold record for sales in Scandinavia. Then-former and now current guitarist Brett Gurewitz disliked the album, however, and commented that it was "BR's worst-selling record to date" and described it as "uninspired." He has since taken that back. 
Due to Gurewitz's departure a year before the album was recorded, all tracks for this album were written by Greg Graffin, though guitarist Brian Baker co-wrote 4 out of 15 of the songs.
The track "Cease" was later re-recorded for Greg Graffin's 1997 solo album, American Lesion, this time as a piano and vocal arrangement. This version was played by Graffin on their 2006 DVD Live at the Palladium.
The album liner contains ten portraits of faces in black and white, different versions exist, with different pictures as the front cover.
The album would earn Bad Religion a gold record for sales in Scandinavia and reach # 6 on the German charts for the single "Punk Rock Song".
The songs "Them and Us" and "Ten In 2010" were featured in the game Crazy Taxi.