Album promowała singlami: „The Closest Thing to Crazy”, „Crawling Up a Hill” i tytułową piosenką. W 2004 jako jedna z wokalistek supergrupy Band Aid 20 nagrała nową wersję utworu „Do They Know It’s Christmas?”, a dochód ze sprzedaży singla wsparł mieszkańców Etiopii w walce z głodem.
W marcu 2005 wystąpiła z zespołem Queen podczas koncertu charytatywnego ku czci Nelsona Mandeli z cyklu 46664 (granego na rzecz leczenia AIDS). Występ z muzykami grupy Queen uznała za „spełnienie marzeń z dzieciństwa”. Również w 2005 wydała pierwszy w dorobku album koncertowy pt. On the Road Again, zawierający zapis dźwiękowy i filmowy z jej koncertu zagranego w marcu w Fairfield Halls Croydon. W kwietniu odebrała nagrodę Echo za najlepszy debiut roku oraz statuetkę DVD Champion 2005 – Nagroda Artysty Muzycznego za płytę koncertową. We wrześniu 2005 wydała album pt. Piece by Piece, z którym zadebiutowała na pierwszym miejscu listy najczęściej kupowanych płyt w Norwegii oraz dotarła na szczyt list sprzedaży m.in. w Polsce i kilku innych krajach Europy. Album promowała singlem „Nine Million Bicycles”, który stał się jednym z jej największych przebojów oraz został uznany największym przebojem w historii muzyki przez czytelników magazynu „Watch and Listen”.