Nowotny spelade för Karlsruher SC innan han kom till Bayer Leverkusen 1996. Där spelade han tio säsonger. Med landslaget deltog Nowotny i EM 2000 och EM 2004 samt VM 2006. Under sin karriär drabbades han ofta av skador och i januari 2007 meddelade han att han avsåg att sluta.