In this paper we argue that a rigorous understanding of the nature and implications of complexity reveals that the underlying assumptions that inform our understanding of complex phenomena are deeply related to general philosophical issues. We draw on a very specific philosophical interpretation of complexity, as informed by the work of Paul Cilliers and Edgar Morin. This interpretation of complexity, we argue, resonates with specific themes in post-structural philosophy in general, and deconstruction in particular. We argue that post-structural terms such as différance carry critical insights into furthering our understanding of complexity. The defining feature that distinguishes the account of complexity offered here to other contemporary theories of complexity is the notion of critique. The critical imperative that can be located in a philosophical interpretation of complexity exposes the limitations of totalising theories and subsequently calls for examining the normativity inherent in the knowledge claims that we make. The conjunction of complexity and post-structuralism inscribes a critical-emancipatory impetus into the complexity approach that is missing from other theories of complexity. We therefore argue for the importance of critical complexity against reductionist or restricted understandings of complexity.