Around March 2004, a friend of the band's paid for 300 copies of a 7" red vinyl single "Graffiti" and later released a vinyl of their tracks ("The Coast Is Always Changing"/"The Night I Lost My Head") that they’d recorded in their house in Fenham. After some time of doing shows around their home town, Steve Beckett of the dance-electronic label Warp Records found one of these records and decided to sign Maxïmo Park to his record label.