In this work we study pebble automata. Those automata constitute an infinite hierarchy of discrete models of computation. The hierarchy begins at the level of finite state automata (0-pebble automata) and approaches the model of one-tape Turing machines. Thus, it can be argued that it is a complete hierarchy that covers, in a continuous way, all the models of automata that are important in the theory of computation. We investigate the use of this hierarchy as a narrative for the teaching of automata theory. We also investigate some fundamental questions concerning the power of pebble automata.