After living for a short while in Scotland, Milner spent most of his youth in Dorset, England at The Thomas Hardye School. It was here that he was exposed to music from an early age and learnt to play the piano. Initially studying classical music, it was the blues and boogie-woogie that captured his imagination and this provided the base for his musical development through jazz and back to classical music. Whilst still at college, Milner began working with British bluesman Todd Sharpville. He was 19 years old when he recorded on Sharpville's "Meaning Of Life" album alongside special guests Mick Taylor, Leo Sayer, and Snowy White. This led to subsequent tours as part of Sharpville's band across the European continent and in the USA.
In the year following his graduation from King's College London with a music degree, Milner was introduced to Gerry Bron, signed a recording contract with Bronze Records and recorded, Walking On Eggshells. This, his second album, was recorded mainly at Gallery Studios with encouragement from the studio's owner and Roxy Music guitarist Phil Manzanera. Taken from the album, the first single was "Unsquare Dance". The video to the single, "You Think You're So Damn Funny" was shown repeatedly on French and German television, helping the album to become the number one selling jazz/blues album in France in May 2005. As well as Milner's songs and arrangements, the album featured five songs co-written with Pete Brown.