He also played guitar for Kate Bush, Elton John and The Pretenders, is known the world over for the song Magic and was once a Bay City Roller.
Despite these achievements, one thing has rankled the legendary Pilot front man for the last five decades.
The Leither, who moved to The Inch at the age of five, says, “After going to The Inch Primary I went to Liberton High and they didn’t really recognise my musical ability, which is still a sore point, because I had it even then.
“I was going home and playing guitar on my own and it hurt me a little when I watched all the academic guys walking up to school with their guitars on their backs, getting guitar lessons, and there was I, at home, teaching myself.”
Initially self-taught, Paton would go on to learn classical guitar, but if his early love of music wasn’t taken seriously by those around him, he soon demonstrated what he was capable of, and still is, as audiences at The King’s, where he is appearing in Allan Stewart’s Big Big Variety Show this week, are discovering.
Now 67, the gently spoken singer/songwriter boasts a career most musicians can only dream of having.
With performing in the family - his mother was a ballroom dancer, his father a singer of Scottish songs in the clubs - music wasn’t an obvious choice for their son, however.
“People would say, ‘I don’t know why you’re pursuing that, you’re not going to do anything with it. Get a job as a mechanic or something.’
“Actually, my mother did just that - I lasted three days. For me it was always music, music, music.
“I didn’t go out with my mates, I just wanted to play my guitar. I wanted to get better and better, that’s where my drive for success came from.”
Leaving school at 16, and having blown his chance to become a mechanic, it was his sister who came to his rescue when she noticed an advert in the Evening News.
“A band called The Beachcombers were looking for a lead guitarist,” he recalls. “I went for the audition with a borrowed Stratocaster and box amp and passed it. That was me, straight into music and from then on it was bands, bands, bands.”
The Beachcombers, hugely popular in Scotland in the 60s, introduced the young Paton to the city’s live music circuit, venues like the Palais de Danse, Top Storey, The International on Princess Street, The Gonk Club and The Gamp.
“There were so many clubs catering for bands then you would be working five or six nights a week,” he reflects.
“It was a kind of apprenticeship, learning how to project yourself on stage was all new to me.
“When you step on stage for the first time it’s quite nerve-wracking. I knew guys who couldn’t even face the audience they were so nervous, but you have to get through it. I still get a little bit nervous but I’ve been told that’s a good thing,” he laughs.
Having a deal with CBS Records under their belt, things looked good for The Beachcombers.
“We got a residency at London’s Marquee Club and released two singles - The Animal In Me, which was Tony Blackburn’s record of the week and Keep Your Love Light Burning.
“We lasted three years, but eventually fell apart. I was living in London at the time so came back home where Tam Paton, no relation, got in touch and asked if I’d like to work with the Bay City Rollers.”
While with the Rollers he met Billy Lyall, who together with guitarist Ian Bairnson and drummer Stuart Tosh would become Pilot.
“When Billy, who was also a really good flautist, and I were Rollers we’d often go to Central Library to get music for classical guitar and flute. One day, after I’d left the Rollers, I arrived just as Billy was coming out of the library.”
Lyall was working as the engineer at Craighall Studios at the time and asked if Paton was still writing songs. He was.
“Billy said, ‘Come down to the studio. I’ll play piano on your songs and you play guitar on mine... that’s how Pilot started.”
Together the pair wrote “loads and loads of songs” from 1972 through to their first big success with Magic in 1974.
“Billy would say, ‘The Studio is free on Tuesday, write a song for Tuesday.’
“That was my incentive, and he would do the same. Of course, when we got to the studio and I heard his song I’d think it was great and have to write a better one.”
When one of those deadlines resulted in Magic, everything changed.
“We actually had a song before Magic called Just A Smile, but it only reached No 31, so was never considered a hit,” laughs Paton.
Of course, having had one hit, you then have to come up with a second.
“Magic was a hit in October ‘74 and by January ‘75 I’d written, recorded and brought out January.
“That was a really quick turn around. EMI got all their presses on it, so they knew it was going to be a hit, but we never expected a No 1.
“For me, as a songwriter, that was it. I’d done it.”
As with so many 70’s bands, things started to go wrong when Pilot had issues with their management, that and the fact Paton was suddenly finding his skills in great demand.
“While I was still with Pilot, Kate Bush asked me to play on her album... that was the start of it. When other producers heard the playing on that album they’d ask who was playing.
“Eventually all this session work started to flood in and that’s what I have been about for the last 30 years now.
In that time he has played for Elton John, on The Pretenders’ hit I’ll Stand by You, and for Chris Rea, Chris de Burgh and Paul McCartney and others.
Then, 10 years ago, a promotor asked to book Pilot.
Today, Paton is the only original member of the band in the line-up - Lyall passed away in 1989, while Bairnson and Tosh now live abroad.
“It makes me feel vulnerable when I think about,” he admits, “but it’s still a huge thrill playing in Edinburgh.
“I actually wrote Magic, January and Just A Smile in my flat in Glen Street, Tollcross, and now Pilot is playing at The King’s, just a stones throw away.
“In fact, Billy lived in Tarvit Street, so it’s a homecoming of sorts, dedicated to his memory.”
Pilot appear in Allan Stewart’s Big Big Variety Show at The King’s Theatre until Saturday