An inside forward, Paton began his senior playing career with Leeds United, returning to Scotland with Jock Stein's Dunfermline in 1961. He stayed ten years with the Fife side, helping them win the Scottish Cup in 1967-68 and reach the final in 1964-65. After over 200 first-team appearances he moved to Berwick Rangers in 1972, although the repercussions of two leg-breaks during his time with Dunfermline forced his early retiral after just five games for the Borderers.
Paton subsequently began a coaching career, initially assisting George Farm at Raith Rovers. He then became a manager in his own right at Cowdenbeath during the 1974 close season. He left Cowdenbeath to take the Raith Rovers job in October 1974, but Paton left this post in March 1975. He then returned to supporting roles, initially at Hearts.
In 1980 he left football to concentrate on business concerns, but returned in 1986 to assist Alex Totten at Dumbarton. He then joined Totten at St Johnstone, who they guided to two promotions in three seasons. Paton was appointed manager of Dunfermline Athletic in 1993. He guided the side to promotion to the Premier Division by winning the First Division championship in 1996. He has since worked for his former assistant at Dunfermline Dick Campbell, when Campbell was manager of Brechin City.