There is an extensive literature on complexity theory authored by natural scientists writing about research fields in which they are themselves active. There is also a growing literature that draws on this work to address leadership concerns and practices, but whose authors are experienced in leadership education rather than in the substantive scientific fields whose findings they report and interpret. We shall refer to this arena as complexity leadership. The initial burst of enthusiasm for complexity management and leadership in the 1990s, as a conceptual framework for informing organisational practice, has not been sustained at its early intensity. However, the field continues to attract interest. The purpose of this paper is to contribute to a discussion of the validity and significance of these ideas for the leadership of organisations. We enable this through a review of the literature, a critique, and some recommendations. The type of questions which we will be raising are: (1) What failings in current leadership theory or practice are claimed to be corrected? (2) How novel, and how plausible, are the leadership prescriptions which are derived from complexity theory? (3) Does complexity theory provide scientific authority for these prescriptions? We find a paradox in the complexity leadership message which, on the one hand, claims to be rooted in complexity theory, but at the same time, rejects key denominators of the hard sciences. Finally, we offer suggestions on how to constructively handle the apparent paradox.