W latach 1965–1968 odbył służbę wojskową. Dostał skierowanie do Floty Północnej na półwyspie Kola, do miejscowości Widiajewo koło Siewieromorska. Nie przyjęto go na statek czy łódź podwodną, ponieważ istniało tajne rozporządzenie: dzieci represjonowanych rodziców nie mogą zostać dopuszczone do tajnych obiektów wojskowych. Szeregowy Jewdokimow przez trzy lata służył w batalionie budowlanym, był przodownikiem wojskowego chóru.
Po demobilizacji wrócił do rodzinnej wsi, poszedł pracować w fabryce opon w Dniepropetrowsku. Zaczął też występować jako śpiewak w restauracji. Wkrótce ożenił się z dziewczyną z Białorusi i przeniósł się do jej rodzinnych stron.
Nie miał muzycznego wykształcenia, dlatego przez dłuższy czas nie mógł zostać etatowym pracownikiem filharmonii. Mimo tego jego muzyczna kariera na Białorusi rozwijała się. Widzowie przyjęli go bardzo życzliwie, bo śpiewał emocjonalnie, co podobało się publiczności. Do filharmonii nadeszło dużo listów z podziękowaniami dla Jewdokimowa. Dzięki wstawiennictwo całego zespołu koncertowego został przyjęty na etat w filharmonii. Od 1975 roku był solistą-wokalistą Filharmonii Mińskiej. Popularność śpiewaka wśród publiczności rosła z koncertu na koncert. Mimo tego Jarosław był świadomy tego, że wokalista potrzebuje też przygotowania zawodowego.