בפעם השנייה, אולג רומנצב מומה למאמן הראשי של נבחרת רוסיה בכדורגל, שהמשיך, כמו בפעם הראשונה, לשלב את העבודה בנבחרת עם תפקידו כמאמן ספרטק. לדבריו, אין טעם להתחיל בהכנות לקראת מונדיאל 2002 כל כך מוקדם, וכי יש לנסות לחטוף כרטיס לאליפות אירופה ובכל מקרה לקחת את הנקודות המקסימליות בשאר משחקי טורניר המוקדמות. כתוצאה מכך, במסגרת ההעפלה ליורו השיגה הנבחרת רצף ניצחונות רב עוצמה של שישה משחקים, ששיאו היה הניצחון על הצרפתים בפריז בתוצאה 3:2. לראשונה בתולדותיה (כולל התחשבות בהופעותיה של נבחרת ברית המועצות), רוסיה ניצחה את אלופת העולם המכהנת במשחק רשמי, ועוד בביתה. זו הייתה גם התבוסה הראשונה של צרפת מאז מונדיאל 1998.
לפני המשחק המכריע עם , נבחרת רוסיה הייתה במקום השני בבית 4 והייתה בהפרש של נקודה אחת מהאוקראינים. רק ניצחון הרוסים במשחק זה היה מבטיח להם העפלה לאליפות אירופה (תיקו יתאים לרוסיה רק אם איסלנד לא תפסיד לצרפת במשחק מקביל — במקרה זה נבחרת רוסיה תשחק בפלייאוף ואוקראינה תעפיל ישירות ליורו ואלופי אירופה לעתיד ואלופי העולם המכהנים היו נושרים לגמרי מהטורניר). חניכיו של רומנצב, ששאפו לקחת את המקום הראשון הנכסף, הבקיעו מול אוקראינה בדקה ה־75 אחרי בעיטה חופשית של ולרי קרפין. עם זאת, בדקה ה-88 אירעה טרגדיה של ממש: אנדריי שבצ'נקו הגיש כדור חופשי לשער ואלכסנדר פילימנוב עשה טעות גסה: השארת השער לפני הבעיטה, הוא לקח את המיקום הלא נכון ואז, ניסה לתפוס את הכדור. הוא נסוג לאחור, נפל על הדשא גורם לשער עצמי. שער זה השאיר את רוסיה ללא יורו 2000, אך גם אוקראינה לא הגיעה לשם כשהפסידה בפלייאוף מול סלובניה.
עם זאת, רומנצב שמר על תפקידו כמאמן. למרות התבוסה הסנסציונית ב-23 בפברואר 2000 במשחק ידידות עם ישראל בתוצאה 1:4, בטורניר המוקדמות למונדיאל 2002, זכתה נבחרת רוסיה במקום הראשון בביתה לאחר שבעה משחקים ולראשונה מזה שש שנים הגיעה לטורניר גדול.
במאי 2002 התקיים במוסקבה טורניר ידידות "גביע LG" בו השתתפו נבחרות רוסיה, אוקראינה, בלארוס ויוגוסלביה. להפתעתם של רבים, הרוסים תפסו את המקום האחרון בטורניר, לאחר ששיחקו בתיקו עם בלארוס 1:1 והפסידו בפנדלים 4:5, ובמשחק על המקום השלישי, הפסידו גם ליוגוסלביה - 1:1 בזמן החוקי, ואז בפנדלים 5:6 (המנצחת בטורניר הייתה נבחרת בלארוס). באחד המשחקים, נפצע אלכסנדר מוסטובוי שלא היה יכול לשחק במונדיאל. בטורניר מונדיאל 2002, רוסיה העפילה לבית שבו היו יפן, בלגיה ותוניסיה. עם זאת, גם במצב כזה הצליחה הנבחרת להעפיל לפלייאוף. הניצחון על תוניסיה 2:0 התברר כשנוי במחלוקת ביותר, למרות שהנבחרות של יפן ובלגיה במשחק מקביל (שהסתיים בתיקו 2:2) הציגו משחק טוב יותר. במשחק מול יפן בדקה ה-39, הקשר של המארחת קאזויוקי טודה הפיל את איגור סמשוב במרכז רחבת העונשין, אולם השופט הגרמני מרקוס מרק לא העניק פנדל, ולאחר מכן, בדקה ה-58, ולדימיר בסצ'סטניך לא הצליח להבקיע מול שער הריק, מה שהוביל לתבוסת הרוסים 0:1. הפסד זה גרם להתפרעויות במוסקבה, ורומנצב ספג ביקורת רבה. במשחק המכריע עם בלגיה, אפילו תיקו היה מספיק לרוסיה כדי לעלות לשלב הבא. המשחק היה שווה, אך בדקות ה-78 וה-82 הבלגים כבשו שני שערים ועלו ליתרון 3:1. לאחר מכן, אלכסנדר קרז'אקוב, שנכנס כמחליף, בישל לדמיטרי סיצ'ב (שגם הופיע על המגרש לא מהדקות הראשונות) שער. בדקה ה-88, סיצ'ב הבקיע שער אחד (2:3), אבל לא היה מספיק זמן ליותר. לאחר מכן, רומנצב חטף ביקורת חריפה על כך שלא רצה לתת לשחקנים הצעירים הזדמנות לשחק את כל המשחק. כבר 40 דקות לאחר סיום המשחק התפטר רומנצב, אך ההתאחדות דחתה את ההחלטה לישיבת הוועד הפועל ב-7 ביולי 2002. נשיא ההתאחדות ויאצ'סלב קולוסקוב ציין לראשונה שאם רומנצב יפוטר, מאמן זר ימונה למאמן נבחרת רוסיה בכדורגל.
בבית ח' סיימה הנבחרת המארחת, יפן, במקום הראשון של הבית, והעפילה לשלב הבא, יחד עם בלגיה.
במקומות האחרונים של הבית סיימו נבחרות רוסיה ותוניסיה בהתאמה, לאחר שהפגינו יכולת חלשה בטורניר.
לאחר מונדיאל 2002.
ב־7 ביולי 2002, ולרי גזאייב, שאימן את צסק"א, מונה למאמן נבחרת רוסיה. בתחילה דווח כי ישלב את עבודתו עם אימון צסק"א רק עד סוף השנה, אך בשנת 2003 המשיך גזאייב להוביל הן את צסק"א והן את הנבחרת הלאומית. בנבחרת הוצבו בפניו שתי משימות עיקריות: להיכנס לשלושת הראשונים ביורו 2004 ולהגיע לשמינית גמר מונדיאל 2006.
משחקי הפתיחה של מוקדמות יורו 2004 התבררו כאחד הטובים בתולדות הנבחרת: ניצחונות אפקטיביים על אירלנד (4:2) ואלבניה (4:1) והמשחק הלא משכנע עם גאורגיה שהסתיים בתוצאה 0:0.בפברואר 2003 זכתה רוסיה בביטחון בגביע ההתאחדות לכדורגל בקפריסין, אך הדבר הטעה את השחקנים לגבי כוחם. באביב הנבחרת פתאום מפסידה לאלבנים 1:3 ולגאורגים 0:1. באותה עת, סגן נשיא ההתאחדות ולרי דראגנוב הצהיר כי מינויו של גזאייב למאמן הראשי של הנבחרת הייתה טעות גסה, שכן הוא מזמן לנבחרת רק שחקנים ממועדון צסק"א ומגייס יותר מדי שחקנים "משלו" לנבחרת הלאומית. לאחר שרוסיה הובסה על ידי ישראל במשחק ידידות ב-20 באוגוסט 2003, הודיע גזאייב על התפטרותו מתפקיד מאמן הנבחרת.
בית 10 במוקדמות יורו 2004.
שווייץ העפילה ישירות ליורו בעוד רוסיה העפילה לפלייאוף היבשתי.
הכשלונות תחת גאורגי יארצב.
למאמן הנבחרת החדש מונה גאורגי יארצב. על פי ההסכם עם ההתאחדות, הוא נשאר בתפקידו עד אוקטובר 2003, וההחלטה על מינויו הקבוע הייתה צריכה להתקבל רק אם רוסיה תזכה במוקדמות יורו 2004. אחרת, ההתאחדות התכוונה לחזור לנושא של הזמנת מאמן זר. ותיקי הכדורגל הרוסי ולרי אסיפוב, ויקטור אונופקו ואלכסנדר מוסטובוי כבר זומנו למשחק הראשון על ידי יארצב, ושאלת החזרה של ולרי קרפין לנבחרת עלתה. את משחקי המוקדמות האחרונים של יורו 2004, בילתה נבחרת הכדורגל הרוסית בעלייה ותפסה את המקום השני בטבלה, כשהיא מפסידה לנבחרת שווייץ והוגרלה לפלייאוף עם נבחרת ויילס. במשחק הראשון מביניהם, שנערך במוסקבה, הסתיים בתיקו 0:0; אבל במשחק השני, הרוסים ניצחו בחוץ בתוצאה 1:0 — אותו משחק נזכר באופן סנסציוני בשערו של ואדים יבסייב עם ראשו בדקה ה-22 ורגשותיו לאחר המשחק תוך שימוש בשפה גסה. בהיסטוריה המודרנית של נבחרת רוסיה, זו הייתה הפעם הראשונה ועד כה היחידה שרוסיה העפילה לטורניר גדול באמצעות הפלייאוף.
הנבחרת הלאומית לא הגיעה ליורו 2004 בהרכב הטוב ביותר שלה: מסיבות שונות, שחקנים מפורסמים רבים לא יכלו להגיע לפורטוגל — בפרט קפטן הנבחרת הלאומית, ויקטור אונופקו, אשר עד מהרה סיים את קריירת המשחק שלו. רוסיה סיימה בבית עם יריבות די חזקות: ספרד, מארחת הטורניר — פורטוגל, כמו גם המנצחת העתידית יוון, שבתחילת הטורניר נחשבה לאחת הנבחרות החלשות. על פי סקר מאותו זמן, 35% מהרוסים האמינו כי רוסיה, למרות כל הקשיים, תוכל להגיע לרבע גמר הטורניר. עם זאת, ביורו 2004, הנבחרת הלאומית לא הופיעה בצורה הטובה ביותר. כבר במשחק הראשון עם ספרד, הפסידה 0:1, מה שגרם לביקורת הן על השחקנים והן על המאמן - לאחר אותו משחק אלכסנדר מוסטובוי הורחק מהנבחרת. הרוסים גם הפסידו במשחק השני עם פורטוגל (0:2) - ממש בסיום המחצית הראשונה של אותו משחק הייתה הרחקה מאוד שנויה במחלוקת של שוער נבחרת רוסיה סרגיי אובצ'ניקוב, ולאחר מכן אוטר קושנאשווילי רץ מחוץ ליציע העיתונות אל המגרש, נתפס על ידי המשטרה המקומית וגורש מהאצטדיון. לאחר שני משחקים, נבחרת רוסיה ירדה מהטורניר מוקדם מהמתוכנן, אך במשחק האחרון שלא הכריע דבר לרוסיה, במשחק הבכורה של דמיטרי קיריצ'נקו, הוא כבש את השער המהיר ביותר בהיסטוריה של היורו כשכבש כבר בדקה השנייה של המחצית הראשונה. כתוצאה מכך, רוסיה ניצחה את יוון בתוצאה 2:1. תבוסה זו הייתה היחידה של היוונים בטורניר, בהם ניצחו באופן סנסציוני. נבחרת רוסיה של יורו 2004 זכורה גם עם מספר שיא של כרטיסים צהובים ואדומים: 15 צהובים ו-2 כרטיסים אדומים.
בסתיו 2004 החלה הנבחרת הלאומית תחת יארצב במאבק על ההעפלה למונדיאל 2006. בתחילת טורניר המוקדמות, רוסיה השיגה תיקו ביתי מול סלובקיה (1:1) אך ספגה תבוסה מוחצת לפורטוגלים בתוצאה 1:7, במשחק שכונה "ליל החרפה". לאחר תיקו בחוץ עם אסטוניה (1:1) במרץ 2005, ההתאחדות לכדורגל עברה טלטלה עם שני פיטורים בבת אחת: ב-2 באפריל נבחר ויטלי מוטקו לתפקיד נשיא ההתאחדות במקום ויאצ'סלב קולוסקוב הוותיק, וב-4 באפריל גאורגי יארצב התפטר.
בית א' ביורו 2004.
הנבחרת המארחת, , פתחה את משחקי הבית עם הפסד ל, אך העפילה לבסוף מהמקום הראשון בבית לאחר שניצחה בשני משחקיה הנותרים. ו, שסיימו את המשחק ביניהן בתוצאת תיקו, השיגו בשלב הבתים מספר נקודות ופער שערים זהה. אמנם, יוון הייתה זו שעלתה לרבע הגמר בזכות מספר גבוה יותר של שערי זכות. רוסיה סיימה אחרונה אחרי שהשיגה ניצחון בודד בלבד, על יוון.
מאמנים מחליפים בתקופה של אי ודאות.
באפריל 2005 מונה מאמנה הוותיק של לוקומוטיב מוסקבה, יורי סיומין למאמן החדש של נבחרת רוסיה; החוזה עמו נחתם לפני סוף 2005. יחד עם זאת, סגן נשיא ההתאחדות ולרי דראגאנוב אמר כי "הופעתו של מאמן זר בנבחרת אפשרית רק לאחר 2008, שכן כיום מאמנים ברמה עולמית פשוט לא יסכנו את המוניטין שלהם".