In many communities of practice, there is growing awareness about the interdependence between organisational outcomes and the impact of leadership discourses (Putnam and Fairhurst 2001; Clifton 2012). Echoes of the trait perspective on leadership can still be felt when the success or failure of a company is stereotypically being assessed in terms of its leader’s rhetorical performance and personal charisma (Bass 1985). While questioning this perspective, the approach in this chapter envisages leadership as an interactive and relational process that occurs in the culture-specific context of an organisation and is marked by the capacity of leaders to deal with global challenges and opportunity-creating changes (Beerel 2009). The focus of the present study is on the discursively articulated performance of leadership during competition-driven organisational change. Drawing on CEO letters to employees of two multi-national companies, Nokia (Finland) and Ericsson (Sweden), a comparative analysis of the challenges of leadership discourse practices is carried out in a discourse-analytical and pragma-rhetorical perspective. Both companies are known to have a strong link to national identity, but over time they have often displayed different leadership strategies in the national and international context . Nokia is part of the modernisation process of Finnish society and related to a strong national narrative of catching up, while Ericsson represents the continuation of a proud industrial tradition where Swedes for decades have been a most advanced nation (Lindén 2012). This comparative study exposes stereotypes and counter-stereotypes that underlie the discursive construction and reconstruction of leadership aimed at ensuring consistent interconnectedness between a company’s values and its competitive performance qualities.