Although the underlying equations governing plasmas are relatively simple, plasma behaviour is extraordinarily varied and subtle: the emergence of unexpected behaviour from a simple model is a typical feature of a complex system. Such systems lie in some sense on the boundary between ordered and disordered behaviour and cannot typically be described either by simple, smooth, mathematical functions, or by pure randomness. The spontaneous formation of interesting spatial features on a wide range of length scales is one manifestation of plasma complexity. The features are interesting, for example, because they are very sharp, spatially intermittent (the distance between features is much larger than the features themselves), or have a fractal form. Many of these features were first studied in the laboratory, and have subsequently been recognized throughout the universe. Examples of complexity and complex structures in plasmas include: