On 23 July 2009, Dostanić was named new manager of Bulgarian champions Levski Sofia, replacing Emil Velev and signing a two-year contract. He remained in charge for less than three months. On 21 March 2010, Red Star Belgrade announced the appointment of Dostanić as manager. He replaced Vladimir Petrović despite the team's leading position in the league after 19 rounds. With Dostanić at the helm, Red Star Belgrade failed to win the title after three years, finishing as runners-up to arch-rivals Partizan. However, the team won the Serbian Cup, defeating Vojvodina in the final.