Fedato began his career as a youth player of Venezia. In July 2012, he joined Serie B side Bari in a co-ownership deal with Catania. Fedato made his first team debut at Bari as a substitute in a 2–1 win against Pro Vercelli on 25 September 2012. In his debut season, he scored 6 goals in 26 league matches for Bari.
On 31 January 2014, Serie A side Sampdoria announced that it acquired the rights of Fedato and immediately sent him on loan to Catania.