ב-17 בנובמבר 1993 פרצה דרמה במוקדמות מונדיאל 1994. נבחרת רוסיה הפסידה במפתיע ליוון בתוצאה 0:1. בדקה ה-70 ניקוס מחלאס הבקיע שער מדויק לפינה הימנית התחתונה של השער, עם סטניסלב צ'רצ'סוב בשער. ממש בסוף אותו משחק, השער של איגור דוברובלסקי לא נספר בשל טענת נבדל מצד השופט — פאבל סאדירין אפילו בעט בכיסא בזעם. לאחר המשחק, נשיא ההתאחדות ויאצ'סלב קולוסקוב אמר לקבוצה בחדר ההלבשה כי "אין שום מקום למשחק כזה באמריקה". בנוסף, הוא אמר כי על פי חוזה החסות עם ריבוק, השחקנים נדרשים לשחק רק בנעלי המותג הזה, וכל המפרים ייענשו ולא ייסעו למונדיאל. בינתיים, שחקנים רבים חתמו על חוזים אישיים משלהם עם חברות אחרות והם שיחקו בנעליים ממותגים שונים. בהקשר זה, באותו ערב חתמו 14 שחקני הנבחרת על מכתב פתוח להתאחדות, בו הודיעו על סירובם להגיע למונדיאל. למרות שאחר כך 7 שחקנים משכו את חתימתם והצטרפו לנבחרת, נבחרת רוסיה לא יצאה לאליפות העולם בארצות הברית בהרכב אופטימלי.
בית 5 במוקדמות מונדיאל 1994.
רוסיה העפילה למונדיאל יחד עם יוון.
מונדיאל 1994.
לאחר שהוגרלה לבית די קשה (כשיריבותיה הן ברזיל, שוודיה וקמרון), הנבחרת לא הצליחה להגיע לפלייאוף. ואם התבוסה לאלופה העתידית — — עדיין יכולה להיות מוצדקת איכשהו, אז ההפסד לשוודיה נראה אז בלתי מוסבר: הרוסים הובילו במהלך המחצית הראשונה בתוצאה 1:0 אחרי שאולג סלנקו נגח מרחבת העונשין. אבל אז תומאס ברולין חבט בו, ואז מרטין דאלין כבש צמד (כפי שהתברר מאוחר יותר, זה לא היה צירוף מקרים בלבד: השוודים תפסו בסופו של דבר את המקום השלישי באליפות). הניצחון על קמרון בתוצאה 6:1 ושיא של חמישה שערים של אולג סלנקו במפגש אחד לא המתיק את מרירות התבוסה, הנבחרת סיימה במקום השלישי בבית עם 3 נקודות והפסידה לארבע נבחרות נוספות שהגיעו לשמינית הגמר. למרות זאת, 6 שערים שהובקע אפשרו לאולג סלנקו להיות מלך השערים של הטורניר יחד עם שחקן , חריסטו סטויצ'קוב.
רוסיה התמודדה בבית ב' במונדיאל 1994:
תקופת ההתחזקות תחת אולג רומנצב.
את מקומו של מאמן נבחרת רוסיה בכדורגל לאחר התפטרותו של פאבל סאדירין בקיץ 1994 תפס אולג רומנצב, שבמקביל המשיך לאמן את ספרטק מוסקבה.
בהנהגתו, הנבחרת החלה בהכנות לקראת יורו 1996 באנגליה, שבו הצליחה יותר מאשר קודם. נבחרת רוסיה הבטיחה שוב עלייה לטורניר הגמר וגם קבעה שני שיאים בבת אחת בהיסטוריה של טורנירי מוקדמות יורו: היא כבשה הכי הרבה שערים והראתה הפרש שערים כולל שהיווה שיא בכל משחקי המוקדמות - 34:5 (מאוחר יותר הובסו שיאים אלו על ידי נבחרת ספרד במוקדמות יורו 2000, שהפרש השערים שלה היה 42:5). עם זאת, היריבות בבית של נבחרת רוסיה היו רחוקות להיות מהחזקות ביותר: בנוסף לנבחרת יוון, עמה הרוסים כבר התמודדו במוקדמות מונדיאל 1994, נבחרות סקוטלנד, פינלנד, איי פארו, כמו גם נבחרת סן מרינו, עליה גברה רוסיה בניצחון גדול בתוצאה 7:0. בסך הכל השיגה נבחרת רוסיה שמונה ניצחונות במוקדמות יורו 1996, חלקה נקודות רק עם נבחרת סקוטלנד (תיקו 0:0 ו-1:1) ולא ספגה תבוסה אחת, מה שאפשר לא רק לעבור מהמקום הראשון לאליפות אירופה, אך גם להראות את התוצאה הטובה ביותר מבחינת הנקודות שנצברו מבין כל הנבחרות האחרות בטורניר המוקדמות.
בשנת 1996 התפטר רומנצב זמנית מאימון ספרטק, תוך התמקדות בנבחרת. בפברואר זכתה נבחרת רוסיה בביטחון בטורניר הידידות של גביע רוטמנס במלטה וניצחה את נבחרות מלטה, איסלנד וסלובניה. ב־29 במאי 1996 הכריז אולג רומנצב על שמות השחקנים שיגיעו לאליפות אירופה באנגליה. הנבחרת נכנסה לאותו בית עם איטליה, גרמניה וצ'כיה. רבים ראו בבית זה את "בית המוות". אבל פרשנים רבים תלו תקוות גדולות בנבחרת, הם טענו שהבית לא היה בלתי אפשרית, מכיוון שהאיטלקים כבר לא הציגו את אותה יכולת מאז גמר מונדיאל 1994, הגרמנים הודחו מרבע הגמר הכושל של מונדיאל 1994 עם בולגריה ולצ'כיה זו הייתה השתתפות ראשונה בטורניר גדול לראשונה מאז התמוטטות צ'כוסלובקיה ונחשבה בין הנבחרות האאוטסיידריות של האליפות. במקביל, בתחילת הטורניר, נבחרת רוסיה דורגה במקום השלישי בדירוג פיפ"א. ברם, שילוב הנסיבות הוביל לקריסה מוחלטת.
במשחק עם איטליה, טעות של השוער סטניסלב צ'רצ'סוב הובילה לתבוסה 1:2; במשחק עם גרמניה נגרמה מכה מוסרית לנבחרת: מתיאס סמר ויורגן קלינסמן הביסו את רוסיה 3:0 (קלינסמן כבש צמד), יורי קובטון הורחק בסיום המשחק וסרגיי קריאקוב הסתכסך עם המאמן אולג רומנצב בגלל היעדרותו מההרכב למשחק עם הגרמנים. למרבה האירוניה, רק במשחק עם צ'כיה, שהביאה לאחר מכן את הסנסציה החשובה ביותר בטורניר — היא הגיעה עד לגמר וכמעט ניצחה בו - רוסיה נחלצה בתיקו 3:3. במשחק עצמוב אחרי שרוסיה הייתה בדרך להפסד במהלך המשחק בתוצאה 0:2, הנבחרת השוותה את התוצאה ועלתה ל-3:2, ולדימיר בסצ'טניך אפילו כבש שער מדהים מ־30 מטרים מול פטר קובא, אך 5 דקות לפני שריקת הסיום, הנבחרת הצ'כית הצליחה להיחלץ מהתבוסה והשוותה. נקודה אחת בשלושה משחקים והתנגשויות עם השחקנים שהפכו לכותרות וכתבות רבות בעיתונות הביאו להתפטרותו של רומנצב ב־11 ביולי 1996. רומנצב אמר כי הוא טעה, לאחר שלקח לנבחרת רוסיה את אלה שבמקום לשחק ניסו לפתור את בעיותיהם האישיות.
אי ההעפלה למונדיאל ורצף הפסדים.
את מקומו של אולג רומנצב תפס בוריס איגנאטייב, שמונה למאמן הראשי לקראת מוקדמות מונדיאל 1998 בצרפת. לפני כן, איגנטיב היה עוזר למאמן הנבחרת במשך 4 שנים, בעבר אימן את נבחרת הנוער, מעולם לא עמד בראש מועדון גדול ובאופן כללי לא נחשב למאמן מנוסה.
לפני תחילת משחקי המוקדמות, הנבחרת הלאומית ניהלה משחק ידידות עם ברזיל, שהסתיים בתיקו 2:2. במשחק זה כבשו שתי הנבחרות פנדל וספגו כרטיסים אדומים. בטורניר המוקדמות למונדיאל 1998 הבית היה פשוט יחסית: עם בולגריה, , קפריסין ולוקסמבורג. נבחרת רוסיה ניצחה במשחק המוקדמות הראשון, ניצחה את נבחרת קפריסין בתוצאה 4:0, ולאחר תיקו חוץ עם ישראל (1:1) וניצחון על לוקסמבורג (4:0), רוסיה תפסה את המקום הראשון בבית. בין משחקי המוקדמות, הנבחרת נסעה להונג קונג, שם נערך טורניר הכדורגל הבינלאומי גביע קרלסברג - טורניר זה היווה הזדמנות להתנסות בהרכב ולפגוש את נבחרות יוגוסלביה ושווייץ. נבחרת רוסיה זכתה בטורניר זה.
עם זאת, אז הנבחרת שיחקה באופן סנסציוני ויצאה בתיקו עם קפריסין 1:1, מה שהטיל ספק ביכולת להעפיל למונדיאל 1998 מהמקום הראשון בבית. שלב המוקדמות הסתיים בשני משחקים בין רוסיה לבולגריה, אליהם הגיעו הבולגרים כשהם בפער של נקודה מרוסיה. המשחק בסופיה זכור כאחד השערורייתיים בתולדות נבחרת רוסיה: השופט הצ'כי ואצלב קרונדל לא שרק מיד לשלושה פנדלים נגד בולגריה בגלל עבירות על סימוטנקוב, קוליוואנוב ויאנובסקי. כתוצאה מכך ניצחה בולגריה 1-0 והבטיחה את המקום הראשון בבית. רוסיה, למרות הניצחון במוסקבה בתוצאה 4:2, לא הצליחה להגיע למונדיאל ישירות מהמקום השני ונאלצה לשחק בפלייאוף. איטליה הפכה ליריבה של רוסיה בפלייאוף. באיטליה ההגרלה גרמה לבהלה — עיתונים יצאו עם כותרות כמו "המונדיאל הופך לסיוט: אנחנו משחקים עם הרוסים". ברוסיה, הסיכויים של הנבחרות היו שונים. התיקו במוסקבה 1:1 הותיר כמה סיכויים ותקוות, למרות שהשוער של האיטלקים אנג'לו פרוצי, שהוחלף באותו משחק בכוכב העולה של הסרייה A ג'אנלואיג'י בופון, נפצע. עם זאת, בנאפולי, האיטלקים לא אפשרו לרוסיה לנצל את סיכוייה וניצחו 1-0 והשאירו את רוסיה ללא השתתפות במונדיאל לראשונה מזה 20 שנה.
נשיא ההתאחדות ויאצ'סלב קולוסקוב ציין כי כל הבעיות של נבחרת רוסיה בכדורגל נובעות מחוסר ספונסר - בשנת 1994 הפכה חברת קלדירולה לספונסר הנבחרת, אך היא סירבה לשתף פעולה לאחר ההופעה הלא מוצלחת במונדיאל 1994; לאחר שגזפרום עשתה אותו הדבר ביורו 1996. למרות שלא העפיל עם הנבחרת לטורניר הגמר של מונדיאל 1998, ההתאחדות הציעה לבוריס איגנאטייב להישאר המאמן עד אוגוסט 1998 ולאחר מכן להאריך את החוזה עד 31 בדצמבר 1999. עם זאת, ב־19 ביוני 1998 הודיע איגנאטייב על החלטתו לעזוב. ב-23 ביולי התקבלה התפטרותו באופן רשמי.
ההתאחדות בחרה פה אחד את אנטולי בישובץ כמאמנה החדש של נבחרת רוסיה, לאחר שאימן בעבר את נבחרות ברית המועצות וחבר המדינות העצמאיות, כולל בטורניר הכדורגל האולימפי ב־1988 שבו הנבחרת זכתה בזהב. הוא קיבל את המשימה להקים הרכב חדש וחזק לקראת מונדיאל 2002. כתוצאה מכך, בישובץ והנבחרת החלו בהכנה לקראת יורו 2000.
ברם, בישובץ הפך למאמן הגרוע ביותר בהיסטוריה המודרנית של נבחרת רוסיה: הנבחרת הפסידה בכל ששת המשחקים בהם הוביל אותה, והאירועים הדרמטיים במהלך משחקים אלה החריפו את הרושם. במשחק המוקדמות מול , לאחר טעות גסה של יורי קובטון, הורחק השוער דמיטרי חרין. במשחק ידידות עם , לאחר שהורחק בשל נגיעת יד של סרחיו ברקהואנה, נשרק פנדל, אך סנטיאגו קניזארס הצליח להגיע לכדור, אותו בעט אלכסנדר מוסטובוי. במשחק עם , עקב התקפה שנויה במחלוקת ברחבת העונשין של היריבה, הורחק אלכסיי סמרטין ובסיום המשחק יורי קובטון העניק ניצחון לאיסלנדים כששלח את הכדור לרשת שלו עם הראש וקבע ניצחון 1:0 משער עצמי. כל זה מסתכם גם בתבוסה הכואבת מברזיל בתוצאה 1:5 במשחק ידידות, בו הנבחרת הלאומית הייתה מיוצגת למעשה בהרכב משני.
כתוצאה מכך, בדצמבר 1998, בדירוג פיפ"א, ירדה הנבחרת הרוסית למקום ה-40 וכמעט איבדה את סיכוייה להגיע לאליפות אירופה, וב-18 בדצמבר פוטר בישובץ בשל "התוצאות הלא מספקות" של הנבחרת הלאומית. הוא שימש כמאמן רק חמישה חודשים.
הקדנציה השנייה של רומאנצב וניסיונו של גזאייב.