Staroechin begon zijn carrière bij SKA Odessa in 1968. Nadat hij in 1971 voor één seizoen voor Boedivelnyk ging spelen bracht hij de rest van zijn carrière door bij Sjachtjor Donjetsk. In 1975 en 1979 werd hij vicekampioen met de club. In 1979 werd hij topschutter van de competitie en werd hij ook uitgeroepen tot voetballer van het jaar. In 1980 won hij met Sjachtjor de beker. Dat jaar speelde hij ook zijn eerste en enige wedstrijd voor het nationale elftal op 7 mei 1980 tegen Oost-Duitsland.
