He was born in Liverpool, but as a child during the 1960s moved to the Cantril Farm district, where future footballer Micky Quinn and future comedian Craig Charles were among his neighbours. He attended St Dominic's 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 and provided some keyboard parts to the band's output.
The band ended three 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".