Wallace började sin fotbollskarriär i Southampton men är mest ihågkommen som en framgångsrik anfallsspelare i Leeds United mellan 1991 och 1998 då han spelade 256 matcher och gjorde 66 mål. Under sin spelarkarriär från 1988 till 2004 spelade han totalt 472 ligamatcher och gjorde 152 mål.[1][2][3]