The South African Middle Stone Age (MSA) has in recent years become increasingly important for our understanding of the emergence of 'modern human behaviours'. Several key innovations appeared in this context for the first time, significantly pre-dating their re-invention in the European Upper Palaeolithic. One of these innovations was heat treatment of stone to improve its quality for the production of stone tools. Heat treatment may even be the oldest well-documented technique used to intentionally alter the properties of materials in general. It is commonly thought of as requiring the skilled use of fire, a high degree of planning depth and complex cognitive abilities. However, to work on these fundamental concepts we need to analyse the techniques and procedures used to heat-treat and we need to understand what they imply. In this paper, we present a direct and expedient comparison between the technical complexities of four alternative heat treatment procedures by coding the behaviours required for their set-up in so-called cognigrams, a relatively new method for understanding complexity based on the problem-solution distance. Our results show that although the techniques significantly differ in complexity, the techniques used in the MSA fall within the range of complexities known from other MSA techniques. Heat treatment in above-ground fires, as it was practised during this period in South Africa, was even one of the most complex techniques at the time of its invention. Early heat treatment can therefore be considered an important behavioural proxy that may shed light on the behaviour and socioeconomic structure of past groups. The implications of this are highlighted by the ongoing debate about 'modernity', 'behavioural flexibility' and 'complex cognition' of early anatomically modern humans in Africa.