Melnychuk worked in Portugal for several years. He was the coach of Portugal national basketball team, from 2000 to 2007. He achieved their first ever qualification for the EuroBasket 2007, leading the way for the best result of the Portuguese Squad, the 2nd round of the tournament. He left the National Team soon after. After that, he was assigned to be the Ukraine national basketball team coach. Melnychuk was unable to avoid elimination of EuroBasket 2009, by finishing in 4th and last place in the Group C. He returned to Portugal to be the coach of FC Penafiel, newly promoted to the Proliga, for the 2009/10 season.