In 2001 he became coach of Hapoel Petah Tikva. In the 2001–02 season the team finished sixth; Gutman resigned in May immediately following the season's conclusion. He subsequently returned to Hapoel Be'er Sheva, and later spent two years coaching Paralimni in Cyprus.
From February 2007 until early December 2007 he coached AEL Limassol before joining Hapoel Tel Aviv as successor to Guy Luzon. He helped the team escape relegation, gradually building the team until they won the Israeli double - Israeli Premier League championship and Israel State Cup - in 2010. The following season he coached the team to its first-ever qualification to the UEFA Champions League group stage. In May 2011, after winning the 2011 Israeli State Cup, he left Hapoel Tel Aviv.