26 grudnia 2012 roku objął prowadzenie reprezentacji UkrainyUA-Футбол. Национальная сборная Украины получила нового главного тренера.. Poprowadził drużynę w mistrzostwach Europy rozgrywanych w tym samym roku, których Ukraina była gospodarzem wspólnie z Polską. Tam Ukraińcy trafili do grupy „śmierci” z wyżej stawianymi Francuzami, Anglikami i Szwedami. Turniej zaczął się niespodziewanie dobrze, od wygranej z jak się później okazało ze słabo dysponowaną Szwecją 2:1. Kolejne 2 mecze, zakończyły się porażkami (0:2 z Francją i 0:1 z Anglią). Ukraina skończyła turniej na trzecim miejscu w grupie wyprzedzając jedynie Szwecję. Fomenko pozostał na stanowisku, aby doprowadzić zespół do następnego dużego turnieju – mistrzostw Świata organizowanych w 2014 w Brazylii. W eliminacjach Ukraina zaprezentowała bardzo dobrą postawę i zajęła w grupie drugie miejsce za Anglikami, co pozwoliło jej wziąć udział w barażach. Tam napotkali kolejnego rywala znanego im z mistrzostw Europy – Francję. Pierwszy mecz wygrany 2:0 zwiastował niespodziankę i wyeliminowanie „Trójkolorowych”. W rewanżowym spotkaniu, grająca na własnym terenie, faworyzowana Francja zagrała zupełnie odmienne spotkanie wygrywając 3:0 i to ona zakwalifikowała się na czempionat. Następne ME w 2016 roku właśnie we Francji okazały się turniejem ostatniej szansy dla szkoleniowca.