Po odejściu na piłkarską emeryturę, Protasow zajął się trenowaniem. W2003 roku poprowadziłOlympiakos SFP do tytułu mistrzaGrecji, a w lecie2005 przeszedł doSteauy Bukareszt z którą wywalczył w2005 roku tytuł mistrzowski wDivizii A. W latach 2006–2008 prowadził rodzinny klubDnipro Dniepropietrowsk, jednak nie zdobył z nim żadnych sukcesów. Potem trenował klubyKubań Krasnodar orazIraklis Saloniki. 19 grudnia 2009 objął stanowisko głównego treneraFK Rostów[1]. 13 maja 2011 po serii nieudanych meczów podał się do dymisji[2]. 12 listopada 2011 podpisał kontrakt zkazachskimFK Astana[3], w którym pracował do kwietnia 2012[4]. W lipcu 2012 stał na czeleDynama Mińsk[5]. W czerwcu 2013 został zwolniony z zajmowanego stanowiska[6]. 10 października 2014 r. został głównym trenerem rumuńskiejAstry Giurgiu[7]. 3 marca 2015 został zwolniony[8].
