Na de flop van haar eerste single It's too late uit 2000 begon Lucie met het schrijven van nieuwe nummers. Sommige daarvan werden door andere (Britse) artiesten opgenomen zoals Will Young, Gareth Gates, Rachel Stevens en de groep Liberty X. In 2003 tekende de zangeres een nieuw platencontract bij Mercury Records waarna ze begon met het opnemen van haar debuutalbum. De eerste single van dat album was de pianoballad What you're made of die begin oktober door Mercury in Engeland werd uitgebracht. Het nummer kwam binnen op de zevende plaats van de Britse hitlijst. De single bereikte in Nederland de tweede helft van de Top 40 met nr. 28 als piekpositie.