fˈɛlæn stˈɑːɹɾᵻd hɪz kɚɹˈɪɹ æz pˈɑːɹt ʌvðə lˈiːdz juːnˈaɪɾᵻd jˈuːθ sˈɪstəm, ænd mˌeɪd nˈaɪntiːn ɐpˈɪɹənsᵻz fɔːɹ lˈiːdz ɪnðə nˈaɪntiːnhˈʌndɹɪd ˈeɪɾi fˈaɪv ˈeɪɾi sˈɪks sˈiːzən, bˌʌt wʌz ɹᵻlˈiːst ˌɔn ɐ fɹˈiː tɹˈænsfɜː baɪ lˈiːdz mˈænɪdʒɚ bˈɪli bɹˈɛmnɚ.
Phelan started his career as part of the Leeds United youth system, and made 19 appearances for Leeds in the 1985–86 season, but was released on a free transfer by Leeds manager Billy Bremner.