After the dissolution of the Soviet Union in 1991, The North Atlantic Treaty Organization (NATO) and the Russian Federation both stated that ‘we no longer see each other as adversaries’. The opportunity for finally making the ‘Common European Home’ come true was present. During the ‘honeymoon’ in the first half of the 1990s, the diplomatic relations normalized, and in 1994 Russia and NATO signed the Partnership for Peace (PfP) agreement, as a first step towards an official partnership. However, after this short period of political prosperity, the relationship again developed to the worse. This master’s thesis aims to examine why Russia and NATO failed to establish a normative partnership, using Martin Smith’s definitions on partnership types. By examining important historical events, official doctrines, existing research on the field and official statements in light of realism and constructivism theory, I try to illuminate whether the problems with collaborating may be explained by a mutual military fear of each other that could be traced back mainly to the Cold War; or if it is due to a considerable difference in political culture, norms and values due to their distinct history. This thesis should offer an insight to the rather fluctuating relationship between Russia and NATO in the post-Cold War history, and explain reasons for why this is. It will also offer an indication of what kind of political and diplomatic actions NATO and Russia have to undertake in the future in order to develop a normative partnership, if that is what they desire.