Пробиваться на мундиаль пришлось через сито стыковых матчей. Казалось, что выпавшая Словения (49-е место в рейтинге ФИФА на тот момент) не станет проблемой. Однако дома Россия выиграла 2:1, а в гостях Словения взяла реванш и победила 1:0. По сумме двух встреч счёт был 2:2, но правило гола на чужом поле вывело словенцев на чемпионат мира. Игра в Мариборе стала одной из худших в истории сборной — команда не могла попросту взломать словенскую оборону, а масла в огонь подливали норвежские арбитры, которые удалили двух игроков сборной России и подозрительно часто закрывали глаза на нарушения словенцев, игравших предельно грубо. Возмущение по поводу судейства было настолько большим, что российские фанаты, взяв в качестве повода брошенный с трибун нож во вратаря, потребовали от ФИФА немедленной дисквалификации сборной Словении, пытаясь на фоне скандала из игры Франция—Ирландия любой ценой попасть на чемпионат мира. Однако ФИФА даже не начала рассматривать этот вопрос. В результате бывшая сборная СССР вновь не поехала на мировое первенство и впервые с 1978 года пропустила два чемпионата мира подряд.
Главный тренер сборной России Гус Хиддинк заявил после игры, что «пока не принял решения» о продолжении работы в сборной (его контракт заканчивался к июлю 2010 года). Футбольный комментатор Василий Уткинтогда же сообщил, что Хиддинк покидает свой пост. Болельщики развернули кампанию под лозунгом «Гус Хиддинк, останьтесь!», и до января 2010 года существовала вероятность продления контракта между РФС и Хиддинком. Но 13 февраля 2010 года на сайте РФС появилось официальное сообщение об уходе Гуса Хиддинка по завершении предусмотренного контрактом срока, а через четыре дня стало известно о подписании Хиддинком с 1 августа двухлетнего контракта со сборной Турции.
В обновлённом рейтинге ФИФА Россия опустилась на 13-е место. Новый президент РФС Сергей Фурсенко пообещал сделать российскую сборную чемпионом мира в 2018 году, «а после этого закрепиться на ведущих позициях в рейтинге ФИФА». Последний матч под руководством Гуса Хиддинка сборная России провела 3 марта в Дьёре, сыграв с венграми вничью 1:1; финансовые вопросы контракта с тренером урегулировали в июле 2010 года. Своеобразной итоговой оценкой работы голландского тренера на посту стали слова министра спорта Виталия Мутко:
Со своими задачами Хиддинк, я считаю, справился, хотя непопадание на ЧМ-2010 — это, конечно, неудача. Но главное — он поменял отношение к футболу в стране и к нашей сборной в мире. Любой матч с его участием, любая презентация, пресс-конференция, жеребьёвки — всё это работало на имидж российской команды. Когда Хиддинк принял сборную, она находилась в рейтинге ФИФА на 39-м месте, а потом поднялась до 6-й позиции. На жеребьёвке отборочного этапа Евро-2012 Россия была уже в первой корзине. Это дорогого стоит.
Дик Адвокат: повтор ошибки десятилетней давности
В апреле 2010 года в СМИ появились первые сообщения, что сборную России по футболу на посту главного тренера возглавит другой голландец, Дик Адвокат, известный россиянам по работе в санкт-петербургском «Зените».
Контракт с Адвокатом был подписан РФС 15 июля 2010 года по схеме «2+2» с возможным продлением осенью 2011 года. Финансовые условия не обнародовались, но СМИ предположили, что речь идёт о 3—5 млн евро + премиальные за победу сборной России на ЧЕ-2012 до €7 млн. Официальным спонсором сборной на 2010—2011 годы стал «Норильский никель», гарантировавший поддержку в сумме до $12 млн в год, но вскоре заявивший о возможном отказе от гарантий: несмотря на удачную для России отборочную группу, специалисты не считали выход России в финал Евро-2012 гарантированным. Позитивными качествами нового тренера специалисты назвали его разумную жёсткость с игроками и налаженное взаимопонимание с главой РФС Сергеем Фурсенко.
Адвокат решил оставить, в основном, прежний состав сборной, строить игру по схеме «4-1-2-3», ввести «сухой закон» для всех футболистов на всё время сборов, обеспечить команде домашние игры на натуральном покрытии, заняться воспитанием молодых футболистов, увеличить число товарищеских матчей, а в дни отборочных игр существенно ограничить общение футболистов с прессой, что после матча с Андоррой 3 сентября 2010 года некоторые журналисты расценили как бойкот СМИ из-за неподобающего поведения российских болельщиков.
В отборе к Евро-2012 сборная России попала в группу к Ирландии, Армении, Словакии, Македонии и Андорре. Этот квалификационный турнир сборная выиграла без особых проблем, потерпев лишь одно поражение от Словакии со счётом 0:1 — сборная России впервые за 10 лет завоевала путёвку на крупный чемпионат с первого места в группе. На начало чемпионата Европы беспроигрышная серия сборной России составляла 14 матчей, включая сенсационную победу со счётом 3:0 в товарищеском матче над будущими финалистами Евро — сборной Италии.
На финальном турнире ЧЕ-2012 соперниками россиян по группе стали Чехия, Польша и третий раз подряд Греция. Однако сборная России оказалась почти в такой же ситуации, как и десять лет назад на чемпионате мира в Японии: самая простая группа (если судить по рейтингу ФИФА сборных-участниц) с участием хозяев турнира, возможность ничьи в последнем туре и при этом нежелание главного тренера радикально менять состав и вводить новых игроков. В стартовом матче россияне мощно обыграли сборную Чехии со счётом 4:1 — уже после него многие были уверены, что Россия спокойно выйдет из группы и имеет весьма неплохие шансы на повторение «чуда» 2008 года. Однако во второй игре против хозяев из Польши россияне неожиданно для многих сыграли вничью 1:1, но шансы на выход в плей-офф всё равно оставались довольно приличными. В третьем матче им достаточно было сыграть вничью с Грецией, но и здесь сборная России наступила на те же грабли, что и на ЧМ-2002 в матче с бельгийцами: главный тренер категорически отказался вводить молодых игроков в состав команды, и сборная проиграла решающую встречу со счётом 0:1. Греки забили единственный гол на последних секундах первого тайма, вышли в четвертьфинал и выбили Россию из турнира. К слову, поражение от Греции позволяло россиянам выйти в плей-офф в случае ничьи в параллельном матче Польша-Чехия, но в той встрече единственный гол забили чехи, которые также вышли в четвертьфинал. Стоит также отметить, что здесь не в пользу сборной России сыграла ещё и обновлённая система группового этапа Евро, согласно которой при равенстве очков у нескольких команд преимущество имеет та, которая набрала больше очков в матчах со своими конкурентами (а не та, у которой лучшая разница мячей).
Выступление сборной России на Евро-2012 было омрачено сразу двумя скандалами. Во время матча с Чехией российские фанаты устроили массовую драку с охраной Городского стадиона во Вроцлаве, в результате чего РФС был оштрафован на 120 тысяч евро, а сборная России была условно лишена шести очков в квалификации к Евро-2016. Однако впоследствии после аппеляции РФС УЕФА отменила это решение, но потребовала от РФС проведение трёх отборочных матчей Евро-2016 с участием сборной России при пустых трибунах. Кроме того, после поражения от греков в отеле «Бристоль» группа россиян во главе с депутатом Государственной Думы Антоном Беляковым подошла к капитану сборной Андрею Аршавину и завела с ним разговор, в ходе которого он заявил: «То, что мы не оправдали ваши ожидания — это не наши проблемы. Это ваши проблемы. Когда буду в Думе, тогда и отчитаюсь перед вами. Мы проиграли, потому что не забили, а греки забили. От этих разговоров результат всё равно не изменится». Эти слова вызвали широкий общественный резонанс, в свете которого уважение болельщиков к Аршавину было сильно потеряно, однако отчислен из сборной он не был. Сам Дик Адвокат отказался приносить извинения за результат и заявил, что не видел ни одного плохого момента в игре сборной России, за что его также подвергли сильной критике.
Ещё до начала Евро-2012 было объявлено, что контракт Адвоката с РФС продлён не будет, и таким образом матч с греками стал последним матчем голландца у руля сборной. 25 июня президент РФС Сергей Фурсенко, который взял на себя вину за провальное выступление, также покинул свой пост. Новым президентом РФС 3 сентября был избран бывший футболист московского «Динамо» Николай Толстых.
Фабио Капелло: квалификация к ЧМ-2014
После ухода из сборной Дика Адвоката в прессе появились слухи о том, что следующим наставником сборной может стать итальянец — либо главный тренер «Зенита» Лучано Спаллетти, либо бывший тренер сборной Англии Фабио Капелло. В результате 16 июля 2012 года представитель РФС заявил о том, что уже официально подписан контракт с Капелло, и он готов приступить к работе в сборной России. Однако 18 июля РФС официально объявил, что переговоры с Капелло пока продолжаются, но уже на следующий день итальянский специалист согласовал все условия контракта. 26 июля с ним был подписан контракт по схеме «2+2». Капелло принял решение жить в России на постоянной основе, а не приезжать периодически, как это делали Гус Хиддинк и Дик Адвокат. В интервью газете «Спорт-Экспресс» тренер пообещал, что сборная обязательно поедет начемпионат мира в Бразилию.
Свой первый матч обновлённая сборная под руководством Капелло провела неубедительно: в товарищеской встрече с Кот-д’Ивуаром россияне сыграли вничью 1:1. Единственный гол россиян был забит на 55-й минутеАланом Дзагоевым, а через четыре минуты Капелло заменил его на Андрея Аршавина. Эта перестановка вызвала крайне негативную реакцию среди болельщиков на трибунах «Локомотива», которые встретили Аршавина протяжным гулом. Однако впоследствии стало известно, что Аршавин не будет играть первые матчи квалификации к ЧМ-2014 по семейным обстоятельствам. По этой же причине сборную уже официально покинул вратарьВячеслав Малафеев, защищавший ворота сборной на Евро-2012.
В отборе к ЧМ-2014 сборная попала в группу к Португалии, Израилю, Северной Ирландии, Азербайджану и Люксембургу (примечательно, что с Люксембургом россияне встречаются уже в пятый раз в отборах к чемпионату мира). Первый круг отборочного цикла вышел весьма удачным: сборная выиграла все четыре стартовых матча, забив в сумме восемь голов и не пропустив ни одного. В частности, в домашнем матче с Португалией, шансы в котором оценивались весьма неоднозначно, россияне неожиданно вырвали победу со счётом 1:0 (единственный гол уже на 6-й минуте матча забил Александр Кержаков), при том, что гости имели огромный процент владения мячом, а россияне слишком часто ошибались в передачах. Кроме того, после первых четырёх туров Россия является единственной европейской командой отборочного турнира ЧМ-2014, не пропустившей ни одного мяча (перед этим 100-процентный показатель голов имели также Испания и Румыния, но Румыния проиграла Нидерландам со счётом 1:4, а Испания сыграла вничью с Францией 1:1, пропустив гол на последних секундах матча).