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.
New York is Faith's most successful single to date, charting in the top forty in six different countries. The song debuted on the UK Singles Chart at 21, the following week, it fell to 31, then rose 16 places to 15 on its third week, which became its peak position. It stayed eleven weeks in the UK chart.
The song had moderate success elsewhere, reaching number 54 in Germany, 12 in Ireland, 13 in Switzerland, 8 in Finland, 29 in Denmark and number 28 in Sweden.
The video sees Paloma with her fictional boyfriend Tyrone having fun at a bowling alley. Both of them are bowling partners initially seeing them holding championship trophies that they won together. As Paloma sings we get a scene or Paloma in a cross between New York City and the Bowling Alley crossed with each other, as Tyrone starts to lose interest in Paloma and having some doubts. In one scene Paloma uses a bowling ball to pretend she was pregnant as she gets Tyrone to kiss the bowling ball, however the next scene later he tells her that he's leaving her for New York. She then lets her boyfriend leave as another shot of Paloma is shown crossed with the Brooklyn Bridge and Statue of Liberty in the background this time, with her boyfriend now in a new team as he bowls with them. However Paloma doesn't want to move on as she remembers the good time they had as he bowls some scene of New York flashes inbetween her, Tyrone and both of them together. She then walks along the bowling lanes as the bowlers play on as she then walks over to where Tyrone is and finds out that he's with another woman who is also pregnant, doesn't fancy bowling as he does but Paloma is just disgusted with him and just moves on as the merging of New York and the Bowling alley fades back to the Bowling Alley with Paloma sitting on one of the lanes as the camera fade off to black.
The music video was shot at a London bowling alley and features professional bowlers. The director was Vaughan Arnell, who also directed the video to Robbie Williams' song, Bodies. The video was released on 2 August 2009.
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.