Arnhem Land, which has one of the longest records of human activity on the Australian continent, also holds one of the most important assemblages of rock art in the world. Indigenous artistic practice in this region has continued since before the Last Glacial Maximum through to the modern day, a period of at least 28 thousand years, during which time the region has undergone significant environmental and palaeogeographical changes. Rock art research in the area, however, has not  considered high resolution palaeolandscape data, but rather has used coarser scale regional environmental models. This paper addresses this issue, applying detailed palaeogeographic modelling of current and former landscapes in the Red Lily Lagoon region in eastern Arnhem Land, to the spatial analysis of rock art site placement in this important cultural landscape. The resultant elevation, land cover and visibility modelling reveal significant changes in site placement strategies for rock art in the region, which appear to relate to four key phases of the landscape change that have occurred from the late Pleistocene to the late Holocene.