Walker spielte zunächst in der FusionbandRiver People, seit Mitte der 1980er-Jahre im Quartett des Vibraphonisten Alan Butler. Daneben trat er in der Band von Michael Gibbs und der Bigband von Kenny Wheeler auf. Mit dem Pianisten Roy Powell gründete er die FusionbandSome Other Country, der der Bassist Gary Culshaw und der Schlagzeuger Steve Gilbert angehörten. In den späten 1980er Jahren bildete er mit Nikki und Richard Iles die Band Emanon.
Zur gleichen Zeit spielte er auch in der Band von Sylvan Richardson, wo er den Saxophonisten Iain Dixon kennenlernte. Walker, Richardson, Dixon und der Schlagzeuger Mikey Wilson bildeten später die Band Brazil Nuts.
Während eines Auftritts mit Kenny Wheelers Bigband in Zürich lernte Walker Julian Argüelles kennen, dessen Quartett er beitrat. In den frühen 1990er Jahren tourte er mit verschiedenen Gruppen von Tommy Smith, u. a. einem Quartett mit dem Bassisten Mick Hutton und dem Schlagzeuger Ian Froman bzw. gelegentlich mit Niels Lan Doky und Jason Rebello.
2008 veröffentlichte Walker sein Debütalbum Madhouse and the Whole Thing There.[1] Im selben Jahr wurde er beauftragt, eine Komposition für das Manchester Jazz Festival zu schreiben; die resultierende Suite Ropes wurde dort erfolgreich aufgeführt (und erschien 2018 als Tonträger). 2010 nahm er mit Adam Nussbaum, Steve Swallow und Gwilym Simcock das Album The Impossible Gentlemen (Basho Records) auf, dem 2013 ein zweites Album Internationally Recognised Aliens folgte.[2] In Deutschland tourte er auch mit der Gruppe Tria Lingvo (das aus Johannes Lemke, André Nendza und Christoph Hillmann besteht).[3]
