The original line up of Mötley Crüe, which consisted of singer Vince Neil, bassist Nikki Sixx, drummer Tommy Lee and guitarist Mick Mars, had reunited for the Generation Swine album and tour in 1997, mainly out of pressure from their management and record company. Even though the group had reunited, problems still existed between Lee and Neil, as Lee felt that the band had been going in a backward direction since Neil rejoined the group. Lee was also having domestic problems with his wife, model Pamela Anderson, which, after an altercation following an argument, led to him serving time in jail.
During this time, Mötley Crüe and Elektra Records severed their 17-year relationship together, with Mötley Crüe gaining full ownership of its music catalog and publishing rights. The break with Elektra allowed the group to form its own label, Mötley Records, to release future projects on.
Lee's legal problems forced the band to decline invitations from Ozzfest and various radio festivals, though the band managed to record two new songs for their 1998 Greatest Hits album, "Bitter Pill" and "Enslaved," which were more in vein of their 1980s output compared to their work during the 1990s.
While Lee was in prison, he decided that he was going to leave Mötley Crüe and start his own project, which eventually became Methods of Mayhem. Lee stayed with the group for the tour of their greatest hits album, but after each show he would retreat to his portable studio and work on material for his new project.
Mötley Crüe teamed up with producer Mike Clink to record the album that Sixx felt should have been the successor to their 1989 album, Dr. Feelgood. With Lee gone, the band hired Neil's longtime friend Randy Castillo, who was Ozzy Osbourne's drummer for 10 years, to take his place.
New Tattoo debuted at No. 41 on the Billboard 200 and slid down shortly after. According to Nielsen SoundScan, the album has sold about 203,000 copies in the U.S. to date. Right before the tour in support of the album, Castillo fell ill with a duodenal ulcer. He was consequently replaced by Hole drummer Samantha Maloney. Two years after the release of the album, Castillo died from Squamous cell Carcinoma, which he was diagnosed with while recovering from stomach surgery.
Lewd, Crüed & Tattooed is a Mötley Crüe concert DVD released in 2001, the concert was recorded live in Salt Lake City on their 2000 tour supporting the "New Tattoo" album. The DVD also features behind the scenes footage and the music video for the single "Hell on High Heels".