תחת סיומין, אחרי שלושה ניצחונות ושתי תוצאות תיקו, רוסיה עדיין הייתה במקום השלישי בבית 3 וכדי להעפיל למונדיאל 2006 בגרמניה הייתה צריכה לנצח את המשחק המכריע עם סלובקיה ואז לנצח בפלייאוף. אבל המשחק האחרון הסתיים בתיקו ללא שערים, ורוסיה סיימה במקום השלישי בטבלה והפסידה לפורטוגל וסלובקיה. עם זאת, למרות שהנבחרת הלאומית לא עלתה לאליפות העולם, תחת סיומין היא מעולם לא הפסידה וזכור במיוחד, התיקו בחוץ עם סגנית אלופת העולם: (2:2).
אחרי עזיבת סיומין, מונה אלכסנדר בורודיוק לממלא מקום. ב-9 בדצמבר 2005, הוא חידש את חוזהו כמאמן, והדגיש שהוא מוביל את הנבחרת הלאומית באופן זמני, עד קיץ 2006. אז, לאחר סיום עונת הכדורגל באירופה, תוכנן להזמין מאמן זר לנבחרת רוסיה.
כדי להכין את הנבחרת לטורניר מוקדמות יורו 2008, ב-1 במרץ 2006, שיחקה הנבחרת משחק ידידות עם ברזיל, שהבטיחה להגיע עם ההרכב החזקה ביותר. נבחרת רוסיה הפסידה 0:1 - כשאת השער היחיד בדקה ה-15 במשחק כבש רונאלדו. באותו משחק, בדקה ה-45, דמיטרי לוסקוב הבקיע לרוסיה, אך השופט השווייצרי מאסימו בוזאקה רשם נבדל והשער לא נספר. הנבחרת הלאומית שיחקה עוד משחק במאי 2006 מול הספרדים ושמרה במפתיע על תיקו ללא שערים. למרות הדומיננטיות של הספרדים ושליטה מוחלטת בכדור, משחקו של השוער איגור אקינפייב אפשר לשמור על שער נקי.
שני מאמנים הולנדים נקראו כמועמדים לתפקיד המאמן הראשי מקרב הזרים - מאמן , חוס הידינק ומאמן , דיק אדבוקאט. הנבחרת הרוסית הייתה אמורה לשחק את משחקי המוקדמות של יורו 2008 עם המאמן החדש בסתיו 2006.
חוס הידינק — המאמן המוצלח ביותר בתולדות הנבחרת.
2006—2008: המסע ליורו באוסטריה ושווייץ.
ב־1 במרץ 2006 הודיע נשיא ההתאחדות לכדורגל ברוסיה, ויטאלי מוטקו כי המאמן ההולנדי חוס הידינק ימונה למאמן החדש של נבחרת רוסיה. ההתאחדוץ לא חששה כי הידינק הוא אחד המאמנים היקרים בעולם עם שכר של כ־4 מיליון יורו בשנה. רומן אברמוביץ' התנדב לתת חסות למשכורתו באמצעות קרן האקדמיה הלאומית לכדורגל שלו. באפריל הסתיים המשא ומתן וב-14 באפריל 2006 נכנס הידינק לתפקיד רשמי לתקופה בת שנתיים.
הידינק ציין כי בטורניר המוקדמות ליורו 2008, רוסיה נכנסה לבית קשה, והוא אינו יכול להבטיח שהנבחרת הרוסית תגיע ליורו. על פי סקר דעת קהל מאותה תקופה, רק 28% מהרוסים האמינו שתוצאות נבחרת רוסיה ישתפרו עם הגעתו של מאמן חדש.
משחקי הפתיחה של מוקדמות יורו 2008 לא הבטיחו הרבה: תיקו מול קרואטיה (0:0) וישראל (1:1) הולידו שמועות על עזיבתו של הידינק ואובדן האמון של מוטקו בו. עם זאת, הניצחונות על האסטונים והמקדונים בתוצאה 2:0 אפשרו לדחות שאלות כאלה לזמן מה. במרץ 2007 הובסה אסטוניה שוב (ושוב בתוצאה 2:0), ואחריה תבוסת אנדורה (4:0) ותיקו מול הקרואטים (0:0) ביוני. בספטמבר התחיל השלב המכריע — ראשית, רוסיה נאלצה לשחק מול המקדונים עם עשרה שחקנים (3:0), אבל אחר כך הבריטים הביסו את רוסיה באותה תוצאה בוומבלי. גורלה של הנבחרת היה תלוי במשחק מול אנגליה במוסקבה. או-אז רוסיה ניצחה 2-1 ועשתה צעד גדול לקראת יורו 2008. חודש בדיוק מאוחר יותר בישראל, הרוסים הפסידו באופן סנסציוני בדקות האחרונות בתוצאה 1:2. כדי להיכנס לאליפות אירופה, הרוסים היו צריכים להביס את אנדורה 4 ימים לאחר מכן, אך גם לקוות לניצחון הקרואטים בלונדון על אנגליה. ומה שאוהדי הכדורגל הרוסים בקושי האמינו בו אכן התממש: קרואטיה, שכבר הבטיחה העפלה ליורו, ניצחה 3:2 בלונדון, בעוד הרוסים בקושי ניצחו באנדורה בתוצאה 1:0 (בעוד ארשאבין הורחק ולאחר מכן החמיץ את שני משחקי הפתיחה ביורו). קרואטיה ורוסיה עלו ליורו 2008, בעוד אנגליה לא עלתה לראשונה לאליפות אירופה מאז 1984. כבר במרץ 2008 הוארך החוזה בין הידינק לבין ההתאחדות עד יוני 2010.
באליפות אירופה עצמה, רוסיה נכנסה לאותו בית עם , (שתזכה בטורניר) ו (שזכתה בטורניר הקודם). רוסיה נפגשה עם נבחרות יוון וספרד באליפות אירופה בפעם השנייה ברציפות. ההפסד בתחילת הטורניר לספרדים בתוצאה 1:4 לא הוריד את שחקני הנבחרת מהקצב, וניצחונות על היוונים 1:0 והשוודים 2:0 אפשרו לרוסיה להגיע לפלייאוף של טורניר גדול בפעם ראשונה מזה 20 שנה. היריבה במשחק רבע הגמר הייתה , שניצחה שלושה משחקים בתוצאה כוללת של 9:1 ונחשבה לאחת הפייבוריטיות לזכות ביורו. באותה הזדמנות אמר הידינק: "אני רוצה להיות בוגד השנה בהולנד". המשחק הסתיים בניצחון הרוסים בתוספת הזמן בתוצאה 3:1. כמעט במהלך כל המשחק, הרוסים שלטו במגרש, ובדקה ה-56 הבקיע ראשון רומן פאבליוצ'נקו. חצי שעה מאוחר יותר, רוד ואן ניסטלרוי השווה את התוצאה והכניס את המשחק להארכה. בהארכה, הרוסים לחצו היטב וניצחו בזכות שערים של דמיטרי טורבינסקי ואנדריי ארשאבין.
בחצי הגמר הרוסים שוב נפגשו עם הספרדים, אך לרוסיה לא היה מספיק כוח לסנסציה נוספת — אלופת אירופה העתידית שוב ניצחה את שחקניו של הידינק, הפעם בתוצאה 3:0. נבחרת רוסיה חלקה את המקום השלישי עם ובאוגוסט 2008, לראשונה מזה 11 שנים, נכנסה לדירוג עשר נבחרות הכדורגל החזקות בעולם בדירוג פיפ"א. הידינק הפך למאמן המכובד של רוסיה, השני ברשימת "המאמן הטוב ביותר של נבחרת השנה" אחרי מאמן ספרד לואיס אראגונס והרביעי ברשימת המאמנים הטובים ביותר ב-13 השנים האחרונות. נשיא רוסיה דאז דמיטרי מדבדב אמר שהוא יכול לשקול להעניק להידינק אזרחות רוסית; בתגובה אמר הידינק כי הוא מרגיש בבית ברוסיה וכבר למד את מילות ההמנון הרוסי. האופוריה הייתה בשיאה.
2008—2010: הדעיכה ואי ההעפלה למונדיאל בדרום אפריקה.
במאבק להעפיל למונדיאל 2010, רוסיה הוגרלה לבית עם גרמניה, פינלנד, וויילס, אזרבייג'ן וליכטנשטיין. המאבק על ראשות הבית התפתח בין רוסיה לגרמניה, ובשני המשחקים האחרונים הרוסים השיגו לפחות תיקו עם הגרמנים וניצחו מול אזרבייג'ן, ונראה היה שחניכיו של חוס הידינק היו בדרך להשתתף במונדיאל בדרום אפריקה. עם זאת, הדו-קרב המכריע עם הגרמנים במוסקבה הסתיים בניצחון האורחים בתוצאה 1:0. באותו חודש עזבה רוסיה את דירוג עשר הנבחרות הטובות בדירוג פיפ"א. ההתאחדות מסרה כי התוכניות השאפתניות לא השתנו, ועל פי "האסטרטגיה לפיתוח הכדורגל בפדרציה הרוסית לשנים 2006–2012" נבחרת רוסיה בכדורגל הייתה צריכה:
בתום מוקדמות מונדיאל 2010, רוסיה התבררה כנבחרת הלאומית הראשונה בדירוג הנבחרות שתפסה את המקום השני בבית ולפי השיטה הישנה, רוסיה הייתה עולה אוטומטית למונדיאל, אך הפעם היא נאלצה לעבור דרך משחקי פלייאוף. נראה כי סלובניה החלשה (מקום 49 בדירוג פיפ"א באותה תקופה) לא תהווה בעיה. רוסיה ניצחה במשחק הביתי 2:1 כשספגה שער בדקות האחרונות, אך סלובניה נקמה בביתה וניצחה 1:0. במצטבר, התוצאה הייתה 2:2, אך כלל השער במשחקי חוץ הביא את הסלובנים למונדיאל. המשחק במאריבור הפך לאחד הגרועים בתולדות הנבחרת, שלא יכלה לפרוץ את ההגנה הסלובנית, והשופטים הנורווגים הוסיפו דלק למדורה, עם הרחקת שני שחקני נבחרת רוסיה (אלכסנדר קרז'אקוב ויורי ז'ירקוב) ולעיתים קרובות העלימו עין מהפרות של סלובנים ששיחקו בגסות רבה. הכעס על השיפוט היה כה גדול עד שהאוהדים הרוסים, שלקחו כתירוץ סכין שנזרקה מהיציע לעבר השוער, דרשו מפיפ"א לפסול לאלתר את . עם זאת, פיפ"א אפילו לא החלה לשקול את הנושא הזה. כתוצאה מכך נבחרת רוסיה לא העפילה שוב לאליפות העולם ולראשונה מאז 1978 החמיצה שתי אליפויות עולם ברציפות.
מאמן נבחרת רוסיה, חוס הידינק, אמר לאחר המשחק כי "טרם קיבל החלטה" להמשיך לעבוד בנבחרת (חוזהו פג עד יולי 2010). פרשן הכדורגל וסילי אוטקין הודיע אז כי הידינק עוזב את תפקידו. האוהדים פתחו בקמפיין תחת הסיסמה "חוס הידינק, הישאר!" ועד ינואר 2010 הייתה אפשרות להארכת חוזה בין ההתאחדות להידינק. אך ב-13 בפברואר 2010 הופיעה הודעה רשמית באתר האינטרנט של ההתאחדות על עזיבתו של הידינק בתום התקופה שנקבעה בחוזה וארבעה ימים לאחר מכן נודע כי הידינק חתם על חוזה לשנתיים עם ב-1 באוגוסט.
בדירוג FIFA המעודכן ירדה רוסיה למקום ה־13. נשיא ההתאחדות החדש, סרגיי פורסנקו, הבטיח להפוך את נבחרת רוסיה לאלופת העולם בשנת 2018 "ואחרי זה לצבור דריסת רגל בעמדות המובילות בדירוג פיפ"א". המשחק האחרון תחת חוס הידינק היה ב-3 במרץ 2010, שהסתיים בתיקו 1:1 מול ההונגרים; הנושאים הכספיים של החוזה עם המאמן הוסדרו ביולי 2010.
את ההערכה סופית על עבודתו של המאמן ההולנדי בתפקיד העניק שר הספורט ויטאלי מוטקו:
תחלופת המאמנים הזרים והכישלון של סלוצקי.
דיק אדבוקאט.
באפריל 2010 הופיעו בתקשורת הדיווחים הראשונים כי בראש נבחרת רוסיה בכדורגל צפוי לעמוד הולנדי אחר, דיק אדבוקאט, המוכר לרוסים בזכות עבודתו בזניט סנקט פטרבורג.
החוזה עמו נחתם ב־15 ביולי 2010 עם הארכה אפשרית בסתיו 2011. התנאים הכספיים לא פורסמו, אך התקשורת הציעה כי מדובר על 3-5 מיליון יורו נוסף לבונוס במקרה של ניצחון נבחרת רוסיה ביורו 2012, בגובה של עד 7 מיליון יורו. נותנת החסות הרשמית של הנבחרת לשנים 2010-2011 הייתה חברת נורילסק ניקל, שהבטיחה תמיכה בסך של עד 12 מיליון דולר בשנה, אך עד מהרה הודיעה על סירוב למתן ערבויות אפשריות, אחרי כישלון בטורניר היורו.