In terms of his musical ambitions for the album, in February 2008 Cruz told noted UK R&B writer Pete Lewis of the award-winning Blues & Soul: "I tried to be diverse in my music while not going too far left. Before I go off and hit people with random stuff that they just wouldn't recognise, I'd rather they get to know me first! Which is why I've given them something they can relate to and won't be too difficult for them to grasp, while at the same time not making it generic. Unlike American R&B - which is often really samey a sometimes a bit obvious - I genuinely don't think my record sounds like anybody else."
The first single was "I Just Wanna Know", which was released on 6 November 2006. It hit number 29 on the UK Singles Chart. The second single was "Moving On", which was released on 10 September 2007. The digital download version was released on 3 September 2007. The song did better than the first single by hitting number 26 on the UK Singles Chart. The third single, "Come On Girl" featuring Luciana, was released on 3 March 2008 and hit number 5 on the UK Singles Chart. The fourth single, "I Can Be", reached number 19 on the UK Singles Chart, dated on the chart 25 May 2008, based on downloads sales alone. Furthermore, it has also reached number 23 on the Irish Singles Chart, again on the back of downloads. The fifth single, "She's Like a Star", was released on 11 August 2008. The song peaked at number 20 on the UK Singles Chart.
The Guardian said: "This isn't only manifest in the beats and electronic focus; the album is absolutely drenched in wonderfully camp disco strings. Cruz's own swooping vocals are most reminiscent of Seal; "Never Gonna Get Us" seems permanently on the verge of segueing into Crazy. Though somewhat lacking in low end at times (Cruz should learn about the virtues of a heavy bassline), this is a stylish, inventive debut."BBC noted: "Most of the ballads deploy strings over their R&B rhythms, but "Come On Girl", is all crunchy electro. "Fly Away" starts with a slick electric guitar riff and "I Can Be" recalls '80s British pop soul acts like Joe Jackson or Fine Young Cannibals. Yet Departure is a much more American than British-sounding album, with Cruz's voice blurring into a mid-Atlantic burr." The album entered the UK Albums Chart at number 17 on sales of 11,880. In September 2008, the album was officially certified gold by BPI by reaching 100,000+ sales.