The central thesis of this article is that the evolution of teaching is one of the main factors that lead to increasingly complex communicative systems in the hominin species. Following earlier analyses of the evolution of teaching, the following steps are identified: (i) evaluative feedback, (ii) drawing attention, (iii) demonstration and pantomime, (iv) communicating concepts, (v) explaining relations between concepts, and (vi) narrating. For each of these step the communicative and cognitive demands will be analyzed. The focus will be on demonstration and pantomime, since these seem to be the evolutionarily earliest unique human capacities. An important step is the transition from pantomime for teaching to pantomime for informing and how this in turn leads to communicating concepts. As regards explaining relations between concepts, the focus will be of the role of generics in teaching and communication. Analyzing these topics involves combining cognitive science with evolutionary theory, archaeology and theories of communication. Two factors are important as a background: (i) the evolution of prospective planning, that is, planning for future goals, and (ii) the evolution of a theory mind. These capacities are central in explaining how more advanced forms of teaching, communication and cooperation emerged along the hominin line.