W 2001 roku Jewsiejew przeszedł do lokalnego rywala Spartaka, Lokomotiwu Moskwa. Na początku nie miał jednak pewnego miejsca w składzie Lokomotiwu. W swoim pierwszym sezonie wywalczył Puchar Rosji oraz wicemistrzostwo kraju. W 2001 roku natomiast powtórzył oba osiągnięcia, a już w 2002 roku był podstawowym zawodnikiem moskiewskiego zespołu. Został wtedy po raz pierwszy w karierze mistrzem Rosji, a sukces odniósł także w rozgrywkach Lidze Mistrzów dochodząc z Lokomotiwem do drugiej fazy grupowej. W 2003 roku Lokomotiw był dopiero trzeci w lidze, a w 2004 roku najpierw uległ w 1/8 finału LM AS Monaco, a następnie wywalczył mistrzostwo. W 2005 roku oprócz Superpucharu Rosji Wadim zajął 3. miejsce w lidze, co powtórzył w 2006 roku. W Lokomotiwie wystąpił w 129 meczach i strzelił 16 bramek.
Na początku 2007 roku Jewsiejew zmienił barwy klubowe i trafił do grającego w Pierwszej Dywizji Torpeda, notując tym samym powrót do tego zespołu. Na drugim froncie spędził tylko pół roku i latem podpisał kontrakt z Saturnem Ramienskoje.