Nilsen speelde 32 interlands voor het Noors voetbalelftal in de periode 1990-2000. Onder leiding van bondscoach Egil Olsen maakte hij zijn debuut op 31 oktober1990 in de vriendschappelijke thuiswedstrijd tegen Kameroen (6-1), net als middenvelder Øyvind Leonhardsen (Molde FK). Nilsen nam met zijn vaderland deel aan de WK-eindronde van 1994 in de Verenigde Staten, maar kwam daar niet in actie.