Blue Murder was formed by John Sykes in 1988. As he was partially responsible for the success of their multiplatinum-selling self-titled album, Whitesnake's label Geffen signed a record deal with Sykes following his dismissal from the band.
In the nascent stages of the band, drummer Cozy Powell - with whom Sykes had played in Whitesnake - was attached to the project. Ray Gillen, who had previously sung for Black Sabbath and later for Badlands - not the same band Badlands (née John Sloman's Badlands) that Sykes once played in - sang for an early version of Blue Murder, and reportedly the band recorded demos with him.
Upon comparing the original demos with Sykes singing to the demos with Ray Gillen on vocals, A&R executive John Kalodner encouraged Sykes to handle the vocal duties himself, though Tony Martin (who replaced Gillen in Black Sabbath) briefly worked with the band.
The band was dropped by their label in the mid-90s, at which point Sykes (the only consistent member in the changing line-ups) recorded Out of My Tree in 1995 with Blue Murder members Marco Mendoza and Tommy O'Steen, effectively transforming Blue Murder into an "official" Sykes solo project.