Onder leiding van bondscoach Dušan Galis maakte Šebo zijn debuut voor het Slowaaks voetbalelftal op 15 augustus2006 in de vriendschappelijke wedstrijd tegen Malta (3-0), net als middenvelder Dušan Švento. Hij kende een droomdebuut, want Šebo nam alle drie de doelpunten voor zijn rekening.