He started his career at Ried, but due to and after a little time he was bought from Wels. He has played there for a long time and in the 2007–08 season he was included in the first team as a regular. In this season he has played 30 matches and scored 11 goals.
He has played for the Austrian U-21 team, however he has made declarations to the media that he would not play for Austria, but rather for Albania as it is his dream to play for his own nation.
In addition, when he scored two goals against the Albanian U-21 side in a qualifier match, he refused to celebrate. On that occasion he was wearing red-and-black cleats to honor Albania.
Media reported that he was called by the coach of Albania, Gianni de Biasi, for the friendly match against Armenia, on August 14, but De Biasi did not include him in the final call up. However, in August 20 2013 media reported that Nuhiu has started the procedures to get an Albanian passport in order to be able to represent the senior Albania national team in the future.