Elaborate, religiously sanctioned relationships between people and place are one of the most distinctive features of Aboriginal Australia. In the Australian desert, rock paintings and engravings provide a tangible link to the totemic geography and allow us to examine both changes in the role of individual places and also the development of this system of relationships to land. In this paper we use rock-art to examine the changing history of Puritjarra rock shelter in western central Australia. The production of pigment art and engravings at the shelter appears to have begun by c. 13,000 BP and indicates a growing concern by people with using graphic art to record their relationship with the site. Over the last millennium changes in the surviving frieze of paintings at Puritjarra record fundamental changes in graphic vocabulary, style, and composition of the paintings. These coincide with other evidence for changes in the geographic linkages of the site. As Puritjarra's place in the social geography changed, the motifs appropriate for the site also changed. The history of this rock shelter shows that detailed site histories will be required if we are to disentangle the development of central Australian graphic systems from the temporal and spatial variability inherent in the expression of these systems.