After a successful period with Zimbru Chişinău, Cleşcenco was taken on trial by English club Watford in early 1998. He impressed, but work permit issues, along with Zimbru Chişinău asking for too much money prevented the deal from going through.
In 1999, Cleşcenco joined Maccabi Haifa from Moldovan club Zimbru Chişinău. It was one of the most successful starts ever for a foreigner in Israel as he bagged 22 goals in his first season topping the record set by Polish striker Andrzej Kubica for most goals scored by a foreigner in Israel in a single season. After another strong season in Haifa, he moved to Hapoel Tel Aviv, where he was part of the squad that reached the quarter-finals of the UEFA Cup. He scored one of the goals as they memorably knocked out Chelsea.