Po spadku klubu do Serie B, w letnim okienku transferowym w 2004 roku Włoch podpisał kontrakt z Udinese Calcio. W ataku "Bianconerich" początkowo grał z Davidem Di Michele oraz Vincenzo Iaquintą, później do klubu zostali kupieni tacy zawodnicy jak Asamoah Gyan, Simone Pepe oraz Fabio Quagliarella. Udinese w sezonie 2004/2005 zajęło 4. lokatę w tabeli Serie A i zapewniło sobie awans do Ligi Mistrzów. W Champions League "Bianconeri" zajęli 3. miejsce w rundzie grupowej, przez co rozpoczęli rywalizację w Pucharze UEFA. W rozgrywkach Ligi Mistrzów Di Natale strzelił 3 bramki – wszystkie w dwumeczu z Werderem Brema, natomiast w Pucharze UEFA wpisał się na listę strzelców tylko w pojedynku przeciwko RC Lens.
Z sezonu na sezon włoski gracz strzelał coraz więcej goli w Serie A, a z czasem stał się kapitanem Udinese. Rozgrywki 2007/2008 zakończył z 17 trafieniami na koncie, co dało mu czwarte miejsce w klasyfikacji najlepszych strzelców ligi. W kolejnym sezonie z powodu kontuzji wystąpił tylko w 22 spotkaniach, w których strzelił 12 bramek. 7 lutego 2010 roku Di Natale strzelił hat-tricka w zwycięskim 3:1 meczu z SSC Napoli. W sezonie 2009/2010 w 35 występach zdobył łącznie 29 goli i został królem strzelców Serie A. Wyczyn ten powtórzył także w sezonie 2010/2011 zdobywając 28 goli w 36 meczach Serie A.