The Story Goes...

Después de que a comienzos del 2004 la discográfica en la que estaba, Telstar Records UK, diese en quiebra total, estuvo hasta el 2005 sin discográfica, hasta que a comienzos del 2005 le contratase Warner Records UK, discográfica de Madonna. El disco fue producido por Craig David, Damon Dash, Mark Hill y D. Hill, en el que fue publicado el 22 de agosto del 2005 en el Reino Unido, y justo un día después en todo el mundo.

El disco entró directo al #5 en las Listas de Ventas del Reino Unido, pero justo una semana después cayó al #16. En el resto del mundo, el disco sufrió un fracaso inesperado, siendo el álbum más personal del cantante y de, alguna forma, tendría que vender más discos, pero no fue así, vendiendo menos de 3,000,000 de copias en todo el mundo, lejos de las ocho millones de copias vendidas de su primer álbum "Born To Do It".

Los tres singles que tuvo fueron "All The Way", "Don't Love You No More [I'm Sorry]" y "Unbelievable". El sencillo "All The Way" fue lanzado a finales de julio del 2005, con gran éxito en las Listas de Ventas de todo el mundo, entrando en el #3 en UK, el #5 en Irlanda o el #1 en China. Los dos últimos singles fueron un fracaso, excepto en UK e Irlanda [#4 y #17], pero en el resto del mundo no llegó al Top 40, y el último single no fue publicado a nivel internacional, solo en UK, Irlanda y Australia, fracasando en los tres países.

En los Estados Unidos el disco no se publicó, solo pudiéndolo adquirir a través de iTunes o de otra operadora legal de música por Internet. Las ventas fueron menores a 100 discos en la red. Fue un fracaso.