BBC chart blog gave the song a more positive review than her previous single and rewarded it with 4 stars.
Digital Spy gave the song 3/5 stars and a less positive rating than Stone Cold Sober: 'New York', Faith's follow-up, is a rather more straightforward offering than its predecessor. The lyrics tell the tale of a girl who loses a guy to "another lady", but sadly for Paloma the lass in question isn't a flesh-and-blood adversary, but actually the Big Apple. It's a much bigger target of course, but one that's harder to hit with a swinging vintage handbag. Despite its sweeping strings and soaring vocals, 'New York' is a shade unremarkable compared to her debut, but it still manages to whet the appetite for Faith's upcoming album.
The remix received mixed responses, many critics[who?] said that the song has been ruined by the rap. In 2012, Faith remarked that she thought the collaboration with Ghostface Killah was unnecessary, and that she felt he did not know what the song was about when he wrote the rap accompaniment.
Due the lack of airplay, the song entered the UK Singles Chart at 82 on 7 August 2010. However it then climbed to 44 in its second week on the chart. The original was played on radio during the re-release of this track. It spent five weeks on the chart.