However, according to the band, after flying to New York to debut the album for the record company in the middle of the year, they soon discovered that no one involved in the promoting of their early records was any longer employed by Chrysalis (EMI) records. "When they don't know the names of the songs which made you popular," Strum admitted, "you're in trouble." Leaning on his credentials as the band's producer, Strum ended up getting Slaughter out of its record deal, which added another five unproductive months as the band was seeking a new label. There was interest from five, but Slaughter chose an independent label because Strum thought that "some of the best music was being turned out by the indies". The band signed a deal with then-newcomer, CMC International Records, a North Carolina-based label that supported "American self-written, self-produced rock 'n' roll". According to Strum, "it was definitely a risky decision". "No one knew what was going to happen with CMC at the time, but we were fed up with the corporate thinking of a major label and we liked the hands-on attitude that CMC label president Tom Lipsky seemed to have," he stated. The label also had become the home of '80s hard-rock bands such as Iron Maiden, Warrant, Dokken and L.A. Guns. After many delays, Fear No Evil was finally released in May 1995, in Europe and Japan. Released as hard rock popularity was on the wane, it failed to have the same commercial impact as its predecessors and received mixed reviews from critics. Fear No Evil was characterized as "not boring", compiled of a mix of traditional Slaughter rockers with "the Cult-meets-Lou Gramm and Foreigner sound" of their first single "Searchin'". "Searchin'" was a stretch from their familiar anthemic rock and the expected power ballad and offered "a good introduction of the more diverse musical style the band is growing into". "It'll Be Alright" was described as having "a sure Beatles sound to it", while "Breakdown N' Cry" was noted as Slaughter's first attempt at the blues. "Unknown Destination", the band's final cut, which Strum called their "most aggressive rocker" was influenced by the days when Strum and Slaughter were in a band that toured with Iron Maiden. "The band has grown as people and as musicians, but we still stay true to our kind of music," Strum stated. The band was finally back.