Mayne served his curacy at St John's Harpenden (1957–1959) and then spent six years as chaplain to Mervyn Stockwood, Bishop of Southwark (1959–1965). In 1965, newly married, he became vicar of the Parish of Norton, Letchworth Garden City, where he carried out an effective ministry for the next seven years.
In 1972 Mayne was made the head of religious programmes for BBC Radio and in 1979 he became the vicar of Great St. Mary's, the university church of Cambridge.
During his 50s Mayne was diagnosed with ME and wrote a book about his experiences living with the syndrome (A Year Lost and Found). In 2005 he was diagnosed with terminal cancer of the jaw, and this led him to write a book about his battle with cancer (The Enduring Melody).