This paper starts out from two observations: firstly, that there are complex links between what we term intelligence and what we term creativity and, secondly, that the phenomenon of surprise has a significant role in both the genesis and evaluation of creativity, and is tightly coupled to perception. We argue that for machines to develop to the point where we attribute to them intelligence and, therefore, their own degree of creativity, they must first develop a sensibility of surprise. This, we show, is predicated upon a multi-level organisation of perception, and a method of representing the interest, or novelty, of events and actions taking place in the physical world. A sensibility of surprise further depends on an ability to recognise the novelty of actions the system itself is contemplating. We describe methods of encoding surprise in perceptual robots, and show how this enables them to focus on what is interesting in their environment - a prerequisite to the production of behaviour both creative and intelligent.