Tettey maakte op 22 augustus 2007 onder bondscoach Åge Hareide zijn debuut in het Noors voetbalelftal, in een oefeninterland tegen Argentinië (2–1). Die wedstrijd maakte ook Rune Jarstein zijn debuut als international. Tettey viel in dat duel na 73 minuten in voor Bjørn Helge Riise.