Lee speelde 21 keer voor de nationale ploeg van Engeland, en scoorde twee keer in de periode 1994-1998. Onder leiding van bondscoach Terry Venables maakte hij zijn debuut op 12 oktober1994 in de vriendschappelijke thuiswedstrijd tegen Roemenië (1-1) in Londen. Hij begon in dat duel in de basis en nam in de 55ste minuut de gelijkmaker voor zijn rekening, nadat Ilie Dumitrescu de bezoekers op voorsprong had gezet. Lee nam met Engeland deel aan het WK voetbal 1998.