The concept of paradox has received increasing attention in the study of leadership, but these new ideas have not yet had much influence on empirical leadership research. This paper examines the development of these ideas in the literature and attempts to clarify what influence they might have on empirical research. One general implication of the paradox perspective, that more effective leaders generally display a more complex and varied set of behaviors, is then examined empirically with respect to Quinn’s (Quinn, R. E. 1984. Applying the competing values approach to leadership: Toward an integrative model. J. G. Hunt, R. Stewart, C. Schriesheim, D. Hosking, eds. Managers and Leaders: An International Perspective. Pergamon, New York; Quinn, R. E. 1988. Beyond Rational Management: Mastering the Paradoxes and Competing Demands of High Performance. Jossey-Bass Inc., San Francisco, CA.) model of leadership roles. This model is one of few that allows for an empirical test of some of the central ideas developed by the paradox perspective. The paper also contrasts the recent emphasis on cognitive complexity in the organizational literature (Weick [Weick, K. 1979. The Social Psychology of Organizing. Random House, New York.], Kiesler and Sproull [Kiesler, S., L. Sproull. 1982. Managerial response to changing environments: Perspectives on problem sensing from social cognition. Admin. Sci. Quart. 27548–570.], Streufert and Swezey [Streufert, S., R. W. Swezey. 1986. Complexity, Managers and Organizations. Academic Press, Orlando, FL.]), with the relative lack of attention given to behavioral complexity. Cognitive complexity, the paper argues, may well be a necessary condition for the effective practice of leadership. Behavioral complexity, however, must certainly be the sufficient condition. Leadership must inevitably be performed through action, not cognition, and it would thus appear to be time for leadership researchers to begin to develop theories of behavioral as well as cognitive complexity. The paper also examines several existing leadership theories that are consistent with this point of view (Mintzberg [Mintzberg, H. 1973. The Nature of Managerial Work. Harper and Row, New York; Mintzberg, H. 1975. The manager’s job: Folklore and fact. Harvard Bus. Rev. 5349–61.], Yukl [Yukl, G. 1981. Leadership in Organizations. Prentice-Hall, Englewood Cliffs, NJ.]; Bass [Bass, B. M. 1981. Stogdill’s Handbook of Leadership: A Survey of Theory in Research. Free Press, New York.]), and have (in effect) already offered useful definitions of behavioral complexity. The empirical results of this study come from a study of 176 executives whose leadership role behavior is rated by their subordinates, and whose effectiveness is rated by their superiors. The analysis relies upon a nontraditional analysis technique based on multidimensional scaling that is well suited to this unorthodox analytic problem. The results show that the more effective executives exhibit a greater variety of leadership roles than their less effective counterparts, and that these roles are much clearer to their subordinates. The results also show that more effective executives show much more of the underlying structure of leadership roles proposed by the Quinn model than do less effective executives. Finally, this paper suggests that the concepts of paradox and behavioral complexity are instrumental to a fuller understanding of managerial leadership, and concludes with a discussion of the future research agenda in this area.