Inevitably, tensions between Crow and the remaining members of the group began to arise, especially when Crow was asked on Late Show with David Letterman in March 1994 if the song "Leaving Las Vegas" was autobiographical, for which she offhandedly agreed even though it was actually written by Baerwald and based on the book by his friend John O'Brien. As a result, several members of the Tuesday Music Club group felt betrayed, and O'Brien himself committed suicide not long after. Nevertheless, O'Brien's parents insisted that Crow had nothing to do with the tragedy, noting that he "was just mad about it [...] But the problems that drove him toward the end were – you know, that's a long, long bloody trip."
After Tuesday Night Music Club, Crow wanted to prove her authority as a musician. According to her, "My only objective on this record was to get under people's skin, because I was feeling like I had so much shit to hurl at the tape." Work on the new album began at Toad Hall in Pasadena, California, the same studio where Tuesday Night Music Club was recorded, but sessions were soon relocated to New Orleans, Louisiana because Crow "was feeling ghosts in that room". Bottrell was designated to produce the record and co-wrote three songs that would appear on the album, but eventually left because he could not sort out his differences with Crow. As a result, Crow took over production duties and wrote most of the songs alone or with only one collaborator. She also played most of the instruments on the album, including bass and guitar work and nearly all the keyboard parts. Although most of the album was recorded at Kingsway Studio in New Orleans, Crow returned to California where she could finish it at The Sound Factory and Sunset Sound in Los Angeles.Audio mastering took place at Gateway Mastering Studios in Portland, Maine.
Musically, Sheryl Crow was described as a combination of rock, blues, alternative rock, country, folk, and light hip hop loops. Unlike its predecessor, it also features a more off-balance production and a richer instrumentation, with "lots of fuzz, wurlitzer, hammond, moog. Nothing extreme, perhaps, but almost psychedelic when joined to big mainstream melodies", one critic explained. The album covers topics of American life, relationship breakups, and moralism, among others. For example, "Home" is a folk ballad where Crow recounts the emotional difficulties of a deteriorating relationship, while "Superstar" deals with a woman fantasizing about stardom. The song "A Change Would Do You Good", which features hand claps and organ licks, is about the need to escape a constricted life.
The opening track, "Maybe Angels", was described as "a cryptic ode to UFOs and government conspiracies that plays like an X-Files theme song." Crow explained that the song is "an extraterrestrial yarn that finds Kurt Cobain joining John Lennon in heaven's winged choir". The track "Redemption Day" is a protest against the US indifference to the Bosnian War. It was inspired when Crow visited the country as part of a USO trip with Hillary and Chelsea Clinton. The song was later covered by Johnny Cash, appearing on his 2010 posthumous record American VI: Ain't No Grave. The track "Hard to Make a Stand" references abortion, while "Love Is a Good Thing" criticizes Walmart's gun sales policy with the lyrics "Watch out sister/Watch out brother/Watch our children as they kill each other/with a gun they bought at the Wal-Mart discount stores." The song caused some controversy, resulting in Walmart banning sales of the album at their stores.
Unlike other songs from the album, "If It Makes You Happy" has a simple verse–chorus form, but underwent different arrangements before being turned into a rock song. According to musician Jeff Trott, who co-wrote the song along with Crow, "It started off as a twangy, David Lynch-esque sort of thing. Then [...] we played it like punk rock, really fast, as well as country and funky. You know, you get a song and put clothes on it to see what looks good and what doesn't, and usually when you find the right one it's pretty obvious. With that song it was real obvious!" Trott initially wrote the song when he was in Pete Droge's band, but Crow added a second verse and strengthened the melody.Sheryl Crow also has contributions by notable musicians. For example, "Sweet Rosalyn" features saxophone by Steve Berlin of Los Lobos, while "Everyday Is a Winding Road" features harmony vocals by Neil Finn of Crowded House.
Sheryl Crow was released on September 24, 1996. The album reached No. 6 on the US Billboard Top 200 chart and, as of January 2008, sold 2.4 million units in the U.S. according to Nielsen SoundScan, being certified 3× platinum. In the United Kingdom, Sheryl Crow reached No. 5 on the UK Albums Chart and was certified 3× platinum. A special edition of the album, entitled Sheryl Crow - Signature Tour Edition, was released Australia and Japan in 1997. It contains the bonus tracks "Sad Sad World" and an alternate version of "Hard to Make a Stand" as well as a bonus CD with six songs recorded live at Shepherd's Bush Empire in London on the November 26, 1996. This 2CD set was also released as Sheryl Crow - Special Edition in the United Kingdom in 1997.
Sheryl Crow received general acclaim from most music critics. Eric Weisbard of David Fricke of Spin praised the album's production, stating that the record "goes much further" than its predecessor and that its "bigger beats and dirtier guitar/keyboard effects [work] well with Crow's literate hippie-chick persona". David Browne of Entertainment Weekly stated similar pros, commenting: "If there's such a thing as a professional lo-fi album, Sheryl Crow is it." Writing for Rolling Stone, editor David Fricke highlighted the single "If It Makes You Happy", but criticized "Hard to Make a Stand" for its similarity to "Tumbling Dice" by the Rolling Stones and "Sweet Jane" by the Velvet Underground.