"New Shoes" is the fourth single from Paolo Nutini's debut album, These Streets. It is being used as the headlining single for the US release of the album. It peaked at #108 on the Billboard Hot 100 and at #99 on the US Billboard Pop 100 chart, as well as #21 on the UK Singles Chart.
The song was used for a 2007 international ad campaign by Puma AG.
Lena Meyer-Landrut covered this song on some editions of her album My Cassette Player. A live version is found on the platinum edition of her album Good News and on her DVD "Good News Live".