In the aftermath of the EU’s diplomatic mission to resolve the Orange Revolution in 2004, several Russian policy makers perceived the EU as an aggressive actor which sought to undermine Russia’s influence in the post-Soviet space. About a decade later, Russian policy makers are mocking the EU’s limited abilities in the ongoing Ukraine crisis. The purpose of this article is to explain the reasons for this change of the EU’s abilities by focusing on its state-building in Ukraine. The article examines the EU’s state-building initiatives in Ukraine between November 2013 and July 2015. The article assesses the factors which shape the EU’s state-building in Ukraine. It argues that the EU’s state-building was hampered by two interrelated factors. First, the EU did not possess the policy tools to counter-balance Russia’s affirmative foreign policy towards Ukraine which was reflected in Crimea’s annexation to Russia. Second, as a consequence, this annexation turned Ukraine into a case of contested statehood.