Mayo grew up in Tipton and attended the town's grammar school, but never played football at school and only took up playing as a teenager when he began playing local amateur football. He was spotted by Ken Hodgkisson who signed him for non-league side Dudley Town. However, Mayo "never really thought about" becoming a professional footballer and had begun working as a trainee accountant at Brookhouse Steel where he made copies of ledgers.[2]
While at Dudley, Mayo had an unsuccessful trial with Oxford United before being offered a trial with Walsall. He appeared for the club's reserve side in the Midland Intermediate League before being offered a professional contract in September 1972, at which time he left his accounting job.[2] He made his professional debut for Walsall and appeared in seven league matches for the club but spent the majority of his time in the reserve side. During a reserve match against West Bromwich Albion, the club he supported, Mayo scored a hat-trick which convinced West Brom manager Don Howe to sign Mayo for £17,000 in February 1973.[2] He made his debut for the club in September 1973 as a substitute during a match against Hull City.[3] He made over 90 appearances in all competitions for West Brom,[2] helping the club achieve promotion to the First Division in the 1975–76 season.[3]
In March 1977, he joined Orient along with Allan Glover in a transfer deal that saw Laurie Cunningham move in the opposite direction.[4] A year later, he was part of the Orient side that reached the semi-final of the FA Cup before losing to Arsenal.[2] He joined Cambridge United in September 1981 for a fee of £100,000 where he finished his professional career in 1983.[3]