Wielu wychowanków Romancewa niedługo potem zadebiutowało w drużynie narodowej.

Po nieudanym dla Rosjan Mundialu 1994 do dymisji podał się selekcjoner reprezentacji Rosji Pawieł Sadyrin, a jego następcą został Romancew. Awansował z nią do Euro 1996, ale w Anglii jego podopieczni wywalczyli tylko jeden punkt, po dwu porażkach z Włochami i Niemcami oraz remisie z Czechami. Romancewa oskarżano o faworyzowanie piłkarzy Spartaka oraz kilka nieodpowiedzialnych decyzji kadrowych, jak brak wyboru pierwszego bramkarza i konflikt z liderem ataku Siergiejem Kirjakowem, który po pierwszym meczu wrócił do domu. Po turnieju Romancew złożył dymisję i powrócił do Spartaka.

W latach 1997–2003 klub zdobył kolejnych pięć tytułów mistrza Rosji oraz dotarł do półfinału Pucharu UEFA. W 1999, kiedy Rosjanie słabo rozpoczęli eliminacje do Euro 2000, ponownie został selekcjonerem kadry, nie rezygnując z prowadzenia Spartaka. Romancewa nazywano najpotężniejszym człowiekiem w piłkarskiej Rosji, bowiem w tym czasie był nie tylko trenerem reprezentacji i najsilniejszego klubu w kraju, ale także - od 1997 - jego prezesem.