This article questions assumptions characterizing NATO as focused on ‘hard security’ and the EU as focused on ‘soft security’. By asking how identities and narratives have been constructed in both organizations, subtle differences are brought to light, indicating that changes have taken place in the self-conception and narrative of the two organizations resulting in different conceptions of role and identity. It is suggested that identity and narrative constructions are influenced by practical action and that the EU under ESDP has experienced positive action, leaving it in a stronger position than NATO on questions of ‘hard security’. The analysis utilizes recent empirical evidence in which the EU and NATO are often compared in terms of partnerships and operations. The article shows that in the first decade of the twenty-first century, the EU has been constructing a ‘Tarzan’ narrative, whereas NATO's negative experience in Afghanistan has driven the organization towards a narrative of avoiding failure, emphasizing a ‘Jane’ narrative about partnerships. The pattern may however now be in the process of changing, as evidenced by NATO's robust intervention in Libya, and the EU's preoccupation with establishing the new External Action Service and with the Euro-crisis.