A trilha sonora do filme 'Million Dollar Hotel', com roteiro de Bono, foi feita enquanto o U2 trabalhava no álbum 'All That You Can't Leave Behind'. Bono trabalhava no novo registro do U2, e então ia para o estúdio pra gravar a trilha do filme.
Daniel Lanois, que estava produzindo o disco do U2 na época, disse que foi uma espécie de putaria aquilo, e que ele só ajudou Bono porque era a única maneira de conseguir trazer o vocalista de volta ao estúdio para finalizar 'All That You Can't Leave Behind'.
Daniel Lanois participou da gravação com o U2 da faixa "The Ground Beneath Her Feet" para o filme, que foi originalmente planejada para ser um single.
Mas a Interscope Records se recusou à lançar a música como um single, porque o U2 estava prestes à finalizar seu novo álbum, e os executivos da gravadora não queriam confundir os fãs lançando um single com uma canção que não estaria presente no álbum.
Enquanto gravavam o álbum, o U2 voltou à trabalhar em uma canção inédita que havia sido registrada em uma passagem de som.
Mas esta canção não se encaixa com a sonoridade do novo disco. E como Bono tinha o projeto paralelo da trilha do filme, ele pegou esta nova canção do U2 que iria ser deixada de lado, e passou à ouvi-la sobre uma cena em 'Million Dolar Hotel'.
Com a certeza que "Stateless" não iria fazer parte do corte final para o álbum, Bono solicitou para a banda esta segunda faixa inédita do U2 para a trilha sonora do filme.
Após o lançamento de "The Ground Beneath Her Feet" na trilha do longa, e com um videoclipe filmado, o U2 esperava incluir a faixa também no novo álbum, já que a faixa tinha funcionado bem e sido bem aceita. Mas novamente, houve uma recusa, e a música só foi lançada como faixa bônus do álbum no Reino Unido, Austrália e Japão.