Onder leiding van bondscoach Nils Johan Semb maakte Sørensen zijn debuut voor het Noors voetbalelftal op 8 september1999 in het EK-kwalificatieduel tegen Slovenië (4-0) in Oslo. Hij viel in dat duel na 78 minuten in voor middenvelder Bent Skammelsrud. Sørensen speelde in totaal 21 interlands voor zijn vaderland.