The album title Lullabies to Paralyze was intended to bridge Lullabies with its predecessor Songs for the Deaf by naming it after a line in "Mosquito Song", the final track on Songs for the Deaf. The "deluxe limited edition" of the album includes a bonus track and a bonus DVD containing "a look behind the scenes and special bonus footage". Videos were produced for singles "Little Sister", "In My Head" and "Burn the Witch", and the song "Someone's in the Wolf". The video for "Someone's in the Wolf" was featured on the bonus DVD of Lullabies to Paralyze.
The album was delayed during 2004 because of some changes to the line-up: bassist, vocalist, and co-songwriter Nick Oliveri was fired and on-off vocalist Mark Lanegan went on tour with his own band.
Lanegan can still be heard singing on several songs of the album as well as contributing lyrics. Because of this turmoil, there had been rumours that Lanegan had left the band, which Josh Homme eventually clarified in several interviews was never the case. Nevertheless, he encouraged these rumours to draw the attention off the band by giving the press "something to focus on while I was just making the record".
And at the time, I was like, "Fuck, no one's even listening to this. It's too much about other stuff." And it would have been easy to make Songs for the Deaf 2, which is basically all I heard in my own head. But I can't do that. You've got to shake all that shit away.
The album had two LP pressing runs. The first pressing was released by AntAcidAudio and contains a different cover to the CD version. The sides are named Once, You, Were & Lost, after a line from "Someone's in the Wolf", with each containing a mixture of the CD's album and bonus tracks (with the exception of Once, only the standard tracks are present).
The second pressing is a reissue by Dutch record label Music On Vinyl, released on September 22, 2011. The reissue is different from the first pressing in that it does not have its sides named after the line from "Someone's in the Wolf," and it uses the cover art from the CD release. The reissue omitted bonus tracks "Infinity" and "Precious and Grace" from the track listing, and listed "Like a Drug" as the last track. Side four contains an etching of one of the album's artwork.
The album received generally positive reviews, although slightly lower than its predecessor, the average score being 78 out of 100 on Metacritic based on 31 professional reviews.
Kevin Forest Moreau awarded it 3rd best album of the year 2005, Billboard magazine ranked it 7th best album, Magnet magazine ranked it 9th, and Filter magazine considered it 10th best album of the year 2005.
JustPressPlay ranked it #31 on its list of the Top 100 Albums of the 2000s and named "Tangled Up in Plaid" the 19th best song of the decade.
The "Hidden Outro" later appears as the main riff in the song "Running Joke", a b-side that appears on Era Vulgaris.
The final item on the track list, "The Fun Machine Took a Shit and Died" (located behind the CD in the normal version, or inside the booklet in the deluxe edition), below "Long Slow Goodbye" reads; "The Fun Machine took a shit and died – Was lost or misplaced. (There is a reward for the return of said tapes)". During that time, the band assumed that the tapes of that song were either lost or stolen. A live version of this song can be found on the DVD release Over the Years and Through the Woods. Homme commented, "The tapes got lost. Actually, they were just at another studio, but we falsely accused everyone in the world of theft." The song was later rerecorded as a single and featured as a bonus track on Era Vulgaris.