The distribution of known Pleistocene painted rock art in Island South-east Asia is currently limited to islands on the northern dispersal route to Australia. Here we report the discovery of at least 16 hand stencil motifs in Lene Hara Cave, Timor-Leste; a site on the alternate southern arc route. Superimposition, preservation state, differing 'canvas' materials (i.e. painted surfaces), and the location of the stencils in the internal (darker) part of the cave chamber together suggest that they represent an independent artistic phase that pre-dates the Holocene Austronesian Painting Tradition. The stencils are therefore recognised as a chronologically distinct painted rock art tradition, with a Pleistocene age considered most likely. Such findings have important implications for our understandings on the origins and spread of art in south-east Asia.