As the world of business has become more globalized than ever, organizational leadership and workforce have also become more culturally diverse. Thus, understanding the leadership behaviors and work-related stress perception of employees in different cultures is strategically important for businesses in the 21st century. This paper specifically investigated the task and relationship behaviors as well as the work overload stress perception of working adults in Russia and Vietnam. Using Northouse’s (2007) Style Questionnaire and the Overload Stress Inventory adapted from Hyde and Allen’s conceptual analysis of overload (1996), this study provides a cross cultural analysis of 418 respondents including 230 Russians and 188 Vietnamese based on their place of birth and gender. Vietnamese respondents have significantly higher scores on task, relationship and stress orientations than Russians. However, gender is not a significant factor on task, relationship, and the stress perceptions of these respondents. In this paper, the history and culture of Russia and Vietnam, as well as literature review on the behavioral approaches to leadership and gender role are presented along with practical implications and suggestions for managers, practitioners and future studies.