Sex & Religion reached No. 48 on the U.S. Billboard 200 as well as charting within the top 60 in four other countries. "In My Dreams with You" was released as a single, reaching No. 36 on Billboard's Mainstream Rock chart.
The album's cover art appears to be a reference to the famous artistic depictions of Saint Sebastian.
For Sex & Religion, Vai wished to put together a band of "monster musicians" which included himself, Townsend, drummer and fellow Frank Zappa alumnus Terry Bozzio, and bassist T. M. Stevens. It was originally intended for each musician to contribute ideas and play a large role in the creative process, but Vai ended up micro-managing the whole project, which caused much conflict during the making of the album. As Vai explains, there was heavy expectation to make another album in the style of Passion and Warfare (1990), but he instead made the decision to go in a radically different direction, therefore confounding many fans and critics. The band split up after the album was finished, and Vai subsequently toured only with Townsend and several session drummers and bassists.
Stephen Thomas Erlewine at AllMusic gave Sex & Religion two stars out of five, calling it "the most predictable and conventional—not to mention boring—[album] of Vai's usually remarkable career" and criticizing the band as being "pedestrian".