Following the success of Destination, and the four top ten singles which were released from it, Keating quickly returned to the studio in an attempt to record a follow-up which would replicate the success of Destination. Hooking up with producer Mark Taylor, who had at the time given chart-topping success to Spanish singer-songwriter Enrique Iglesias, Keating also collaborated with long-time collaborators Steve Robson and Steve Mac, as well as writing two songs with former co-writer Gregg Alexander. He also hooked up with American country superstar LeAnn Rimes, who at the time was also signed to his record label, Polydor, to record the duet "Last Thing on My Mind". He also recorded an updated version of "This is Your Song", one of four main recordings of the track, which have featured on Keating's releases across the years. The British version of the album contains three additional tracks, including the hidden track "Getting Started", while the Latin American version of the album features the duet "The Flight", featuring Latin superstar Zucchero, and an updated version of "When You Say Nothing at All", featuring Spanish singer-songwriter Paulina Rubio, which was later released in the United Kingdom as the B-side to the single "Father & Son". Certain copies of the album omit the hidden track "Getting Started", and only include the two international bonus tracks, "I Wouldn't Change a Thing" and "Give You What You Want". Copies can be found with both a blue interior or an orange interior; these are reflected by release territory.
"Lost for Words" was released as the album's lead single on 10 November 2003, peaking at #9 on the UK Singles Chart. The song was co-written by Keating, alongside David Frank and Wayne Hector. The single was backed with the B-sides "I Couldn't Love You More" and "It Was You", as well an acoustic version and a remix by Robbie Rivera.
"Last Thing on My Mind" was released as the album's third and final single on 7 June 2004, peaking at #5 on the UK Singles Chart. A duet with American country superstar LeAnn Rimes, the single was backed with remixes by Metro and Mo Monkey, as well as the music video, which received airplay on VH1 in the United States due to Rimes' appearance.