I will present results from novel analyses of the use of definitions and models in complexity science. In particular, I will show that – while different complexity definitions require different and even exclusive combinations of different criteria – all complexity definitions require contrasting dynamical and phenomenological criteria. Therefore, a contrast between dynamics and phenomenology appears to constitute the conceptual heart of complexity science. I will then propose that the existence of such dynamics-phenomenology contrasts should be used as a minimal definition of the concept of complexity. Furthermore, I assert that the construction of models in complexity science is characterised by a particular structure: many models in complexity science are horizontally constructed and subsequently transferred to specific target systems. Using the results of these analyses, I will argue that complexity science can be viewed as possessing a Kuhnian paradigm.