In 2007 he was called to play for Austria. He served as captain of Austria's U-20 national team at the 2007 U-20 World Cup in Canada where he helped his team to a fourth place finish. After the tournament was over he was the only Austrian voted into the U-20 World Cup line-up by Italian magazine Gazzetta dello Sport.
He made his senior debut for Austria on 30 May 2007 against Scotland. On 26 March 2008, Prödl scored two goals in an international friendly against the Netherlands. On 12 June 2008 during the Euro 2008Austria vs. Poland game he was fouled in the 92nd minute in the penalty area and the referee, Howard Webb, awarded Austria a penalty kick, resulting in their only goal of the tournament.