The Ukrainian crisis demonstrated that lack of trust between major regional security players like NATO and Russia overshadows most regional disputes and conflicts. The article’s main argument is that problems in the two parties’ relations stem from NATO’s and Russia’s existential search for a new role after the end of the Cold War, when their roles and sets of strategies used to be clearly defined. The clash between NATO’s liberal logic and Russia’s realist logic shows that the two players are acting in different systems of coordinates and the minimal common denominator is still to be found.