Goodwin's vocals: "I think the key songs for us on Lost Souls were 'The Cedar Room' and 'Break Me Gently', because they were the first songs Jimi sang properly and we realised we needn't go looking outside the band for this 'mythical singer', something our friend and label boss Rob Gretton had been telling us for years," said Andy Williams. "And once Jimi started we [Andy and Jez] started singing as well. We took years to get there. He recognized something in us and helped us to share it with the world." In late 1998, Doves joined Manchester-based musician Badly Drawn Boy as his backing band; their first release together was the single "Road Movie" in January 1999, recorded live in the studio. Doves also performed on several songs on Badly Drawn Boy's debut album The Hour of Bewilderbeast, as well as accompanied him on tour dates. Doves' second release was the Sea EP in May 1999. A little more than a week before the EP's release, the band's mentor and friend Rob Gretton died of a heart attack. In response, the band dedicated the music video for "Sea Song" to Rob's memory. In August 1999, Doves' third EP Here It Comes was released, with the title track charting at number 73 on the UK Singles Chart. Doves signed with London-based independent record label Heavenly Recordings, and a reissue of the band's debut single "The Cedar Room" was released as the forthcoming album's first single in March 2000. Andy Williams concluded of Lost Souls that, "The best thing was that after all the years of hard work and very testing times we knew we were finally creating the sort of music we had always wanted to ..." The band also dedicated Lost Souls to their late friend and mentor Rob Gretton. With their background in dance and house music, the band incorporated a variety of samples on Lost Souls: "A House" features the sounds of a fire burning, "Lost Souls" features funhouse music, "Break Me Gently" interpolates a sample of a telephone recording that originally appeared on hip hop group 3rd Bass's 1989 album The Cactus Album, and "Sea Song" features a spoken-word dialogue extract from the 1984 Wim Wenders film Paris, Texas. The band also cites Talk Talk's seminal 1988 album Spirit of Eden as a chief influence on Lost Souls. Release and tours Lost Souls was released on