We present a method whereby a robot with no prior knowledge of its sensors, effectors or environment can learn to recognize places with high accuracy, in spite of perceptual alia.sing (different places appear the same) and image variability (the same place appears differently). Previous work showed how such a robot could learn from its experience a useful set of sensory features, motion primitives, and local control laws to move from one distinctive state to another. Such progressive learning of a hierarchical representation is called bootstrap learning. The first step in learning place recognition eliminates image variability in two steps: (a) focusing on recognition of distinctive states defined by the robot’s control laws, and (b) unsupervised learning of clusters of similar sensory images. The clusters define views associated with distinctive states, often increasing perceptual aliasing. The second step eliminates perceptual aliasing by building a cognitive map and using history information gathered during exploration to disambiguate distinctive states. The third step uses the labeled images for supervised learning of direct associations from sensory images to distinctive states. We evaluate the method using a physical mobile robot in two environments, showing large amounts of perceptual aliasing and high resulting recognition rates.