Bár Paloma első albuma, a Do You Want The Truth Or Something Beautiful a brit listákon egészen a 9. helyig kúszott és szépen szerepelt és Európa több országában is szépen szerepelt, az énekes lány kislemezei már korán sem ilyen keresettek. Legutóbbi dala, az Upside Down csupán az 55. helyig jutott hazájában, ezért kiadója az Epic Records úgy döntött, újra kiadja az énekesnő eddigi legnagyobb sikerét, a New York-ot.

A dal első kiadásának idején a 15. helyen debütált és olyan országok listáira is feljutott, mint Franciaország vagy Svédország és Németország. Az Epic pedig úgy gondolta, ha egyszer sikeres volt a nóta, miért ne lehetne másodszor is? Természetesen, a New York egy kissé új köntöst kap második megjelenéséhez, Paloma Faith mellett feltűnik majd a dalban a rapper Ghostface Killah is.

Az énekesnő azonban nem különösebben örül a megjelenésnek. A Popjustice-nak adott interjújában elmondta, sokkal jobban örülne, ha már második lemezén dolgozhatna. Mint mondta: Ha tudni akarod, már nagyon szeretnék az új lemezen dolgozni, de a felsőbb erők mondják most meg, hogy mit csinálhatok.

Egyes források szerint ezen a megjelenésen múlhat Paloma új lemezének jövője, úgyhogy szurkoljunk, hogy sikert érjen el az átdolgozott New York a listákon!