He was born in inner-city Liverpool, but as a child during the 1960s moved to the Cantril Farm district (built to replace inner city slums), where future footballer Micky Quinn and future comedian Craig Charles were among his neighbours.Attended St Dominics Roman Catholic school in Huyton along with his twin sister.
Rutherford joined FGTH in 1980. He sang backing vocals to Holly Johnson and also danced.
The band ended two years later and Rutherford attempted a solo career which was short-lived. In 1989, three singles and the album Oh World were released. Two of the album tracks were produced by ABC. In late 2010, he released the album "The Cowboy Years" under the name "Paul Rutherford/Butt Cowboys".
2011 saw the reissue of the album Oh World and a collaboration with Claudia Brücken, the ex-Propaganda lead singer, on her latest album "Combined"