În 2004, după ce antrenorul echipei Steaua Roşie, Ljupko Petrovic, a demisionat, Rajevac a preluat cârma şi a condus echipa spre două victorii.
Më 2004, pasi dha dorëheqjen Ljupço Petroviç i Yllit të Kuq, Rajevac i zuri vendin dhe e çoi ekipin në dy fitore.