Onder leiding van bondscoach Åge Hareide maakte Høiland zijn debuut voor het Noors voetbalelftal op 22 januari2004 in het oefenduel tegen Zweden (3-0), net als Terje Skjeldestad, Ardian Gashi, Karl Oskar Fjørtoft en Anders Stadheim. Hij speelde in totaal 25 interlands en scoorde één keer voor zijn vaderland: op 1 april2009 in de vriendschappelijke wedstrijd tegen Finland, die met 2-1 werd gewonnen door de Noren.