Осенью 2003 года Блохин принял без сомнения судьбоносное решение и встал у руля сборной Украины, сменив на этом посту Леонида Буряка. Сразу после своего назначения Блохин пообещал, что сборная Украины пробьется на чемпионат мира, причем… с первого места! Это заявление украинская футбольная общественность восприняла как браваду – ведь после распада СССР в 1991 году и создания Федерации футбола Украины национальная команда страны предприняла три попытки пробиться на чемпионат мира, и все окончились неудачей. Да и тот отборочный цикл, еще под руководством Буряка, команда начала далеко не блестяще.

В отборочном турнире чемпионата мира 1994 года в США украинцы не участвовали, поскольку ФИФА еще не утвердила новую систему квалификации с учетом стран – бывших союзных республик. Таким образом, в отборочном турнире играла только сборная России, признанная правопреемницей команды СССР. Тогда целая группа ведущих украинских футболистов (Андрей Канчельскис, Виктор Онопко, Илья Цымбаларь, Юрий Никифоров) даже приняла российское гражданство ради возможности сыграть на чемпионате мира. Остальные вознамерились доказать свою состоятельность в качестве независимой команды.

Первая же попытка пробиться на мировое первенство 1998 года во Франции почти стала для Украины успешной. В своей отборочной группе сборная заняла второе место, пропустив вперед Германию, но опередив Португалию. Однако в стыковых матчах Украина проиграла Хорватии, будущему полуфиналисту мирового первенства.

Ситуация повторилась и в борьбе за путевку на чемпионат мира 2002 года в Японию и Корею. Украина вновь заняла второе место, пропустив вперед Польшу, и попала в стыковых матчах на сборную Германии. Немцы, будущие финалисты чемпионата мира, не оставили команде Валерия Лобановского шансов.

Таким образом, ни выдающийся главный тренер, ни хороший подбор футболистов из его базового клуба – киевского «Динамо» – не помогли украинцам попасть ни на один из крупнейших футбольных турниров. Успех пришел, когда его, по большому счету, никто не ждал. За путевку на чемпионат мира в Германию 2006 года украинцам предстояло бороться с чемпионом Европы 2004 года сборной Греции, бронзовым призером чемпионата мира 2002 года сборной Турции, сильной сборной Дании. Также соперниками украинцев по группе были неуступчивые сборные Грузии и Албании, познавшие, например, вкус побед над сборной России во время отборочного цикла к чемпионату Европы 2004 года.

Однако Блохин сдержал свое обещание, причем в условиях, которые сложно было назвать тепличными. Базовый клуб сборной, киевское «Динамо», все больше места в своем основном составе отдавал легионерам, донецкий «Шахтер» и вовсе ограничивался двумя-тремя украинцами на поле. Хорошей игровой практикой и стабильностью могли похвастаться только динамовцы Александр Шовковский и Андрей Гусин, лидеры «Шахтера» Анатолий Тимощук и Андрей Воробей, а также выступавшие за рубежом форварды Андрей Шевченко из «Милана» и Андрей Воронин из леверкузенского «Байера».

Блохину пришлось сделать ставку на игроков днепропетровского «Днепра», в результате чего получилось так, что игроки команды, которая не слишком удачно выступала в чемпионате Украины, тащили сборную на чемпионат мира. Однако результат был достигнут – в 12 матчах отборочного турнира сборная Украины одержала семь побед, три встречи свела вничью и проиграла лишь две последние, ничего уже не решавшие игры. Команда Олега Блохина стала первой из европейских сборных, пробившихся на чемпионат мира (исключая, естественно, сборную Германии, которая получила это право как хозяйка турнира).

По жеребьевке украинцы попали в группу «H», где кроме них были Испания, Тунис и Саудовская Аравия. Несмотря на то что по рейтингу ФИФА Украина была слабее всех в группе, ей почти все предрекали легкий выход в плей-офф вслед за испанцами, которых считали явными фаворитами.

Первый матч на чемпионате против испанцев для сборной Украины сложился неудачно, она уступила 0:4. Во второй игре против Саудовской Аравии перед зрителями предстала уверенная в себе команда, выигравшая со счетом 4:0. Судьбу путевки в 1/8 финала определял третий матч. Украинцы не форсировали события, в первую очередь старались не пропустить, чем забить. Под занавес матча Шевченко реализовал пенальти и установил окончательный счет – 1:0.

В 1/8 финала украинцев ждал довольно-таки неожиданный соперник – сборная Швейцарии. Швейцарцы обошли французов и заняли первое место в своей группе. Матч прошел в осторожной борьбе, обе команды играли от обороны и не смогли создать в атаке что-либо результативное: основное и дополнительное время завершилось нулевой ничьей. А в серии пенальти вратарь украинцев Александр Шовковский стал первым вратарем в истории мировых первенств, не пропустившим мячей в серии послематчевых пенальти (3:0).

Этот матч смотрела, наверное, вся страна. Что творилось на улицах украинских городов после того, как Шовковский отбил третий пенальти, невозможно описать словами… Это был настоящий праздник единения, когда в порыве счастья были забыты все социальные и политические разногласия – сборная Украины первой среди государств постсоветского пространства пробилась в четвертьфинал чемпионата мира!

Правда, четвертьфинальный поединок со сборной Италии стал для команды Блохина последним матчем на том чемпионате – украинцы уступили со счетом 0:3. Но это поражение сложно счесть неудачей, ведь национальная команда Украины уступила будущим чемпионам мира.

Уже в сентябре 2006 года украинская сборная стартовала в розыгрыше отборочного турнира чемпионата Европы 2008 года. Несмотря на то что соперниками украинцев по группе «B» стали финалисты чемпионата мира сборные Италии и Франции, от команды Олега Блохина ждали только одного – выхода в финальную часть Евро-2008. Поначалу действительно казалось, что Блохин опять сотворит чудо – в первой половине отборочного цикла украинцы одержали четыре победы (в том числе над очень крепкой сборной Шотландии) и потерпели только два поражения – от итальянцев и французов на их поле. Однако затем последовали ничья со сборной Грузии, поражения от итальянцев на своем поле, от шотландцев и от литовцев на выезде. При таких результатах разгром сборной Фарерских островов со счетом 5:0 и ничья со сборной Франции уже ничего не решали – Украина заняла в отборочной группе 4-е место.

1 декабря 2007 года истек срок контракта Блохина с Федерацией футбола Украины, а 6 декабря Олег Владимирович вместе со всем тренерским штабом подал в отставку. Комментируя свое решение об отставке, Блохин заявил: «Я исчерпал себя в сборной. Но обид ни на кого нет, поскольку в провале команды виню только себя. В другие подробности моего желания покинуть пост я вдаваться не буду».

Правда, уже 14 декабря 2007 года Олег Блохин возглавил российский ФК «Москва», который в предыдущем сезоне занял в российской Премьер-лиге 4-е место и вышел в финал Кубка России. Этот российский клуб в какой-то мере является наследником славы московского «Торпедо» – он был создан руководством ОАО «АМО ЗИЛ» под названием ФК «Торпедо-ЗИЛ» после того, как в 1996 году ФК «Торпедо» было продано ОАО «Лужники» и стало называться ФК «Торпедо-Лужники». Зиловцы начали свои выступления с первенства второй лиги и в 2001 году вышли в высшую лигу чемпионата России, однако в 2002 году клуб был продан холдингу «Норильский никель», после чего был переименован в «Торпедо-Металлург», а в 2004 году получил свое нынешнее название. Перед Блохиным была поставлена задача войти в тройку призеров чемпионата, однако в ходе сезона тренер постоянно конфликтовал с генеральным менеджером клуба Юрием Белоусом и ведущими игроками «Москвы», которым не нравился жесткий стиль работы Олега Владимировича. В итоге ФК «Москва» занял в чемпионате 2008 года только девятое место и не смог пробиться в групповой этап Кубка УЕФА, после чего 26 ноября 2008 года Блохин был уволен со своего поста.

На протяжении первых восьми месяцев 2009 года Олег Владимирович находился в отпуске и только 31 августа 2009 года вернулся в большой футбол – он принял предложение стать спортивным директором одесского «Черноморца». Популярная команда сейчас находится в серьезном кризисе, занимая последнее место в чемпионате Украины, и поэтому руководство одесской команды надеется с помощью Блохина поправить свое положение.