Kjetil Rekdal spelade 83 A-landskamper och gjorde 17 mål för Norges landslag.[2] Han debuterade i den högsta norska divisionen blott 16 år och 222 dagar gammal i en match för Molde.
Kjetil Rekdal spelade på 1990-talet i flera år på mittfältet i det norska fotbollslandslaget under förbundskapten Egil Olsen. Rekdal var känd för stor arbetskapacitet och kämpaglöd. Samtidigt var han i hög grad även målskytt. Målen kom ofta från distans, som 1–1-kvitteringen borta på Wembley Stadium i 1993 års VM-kval mot England. I VM-slutspelet i USA 1994 gjorde Rekdal 1–0 (även slutresultat) mot Mexiko i Norges öppningsmatch[4]. Detta var Norges enda mål i 1994 års VM-slutspel. I VM-slutspelet 1998 i Frankrike gjorde Kjetil Rekdal mål på straffspark i Norges tredje gruppspelsmatch - mot Brasilien[5] - sedan toppforwarden Tore André Flo hade hållits fast i straffområdet. Norge vann matchen med 2–1 och gick därmed vidare till andra omgången.[5][6]
Förutom deltagande i två VM-turneringar var Rekdal också med i Norges trupp för EM 2000.[7]