Defining the distinctive capacities of Homo sapiens relative to other hominins is a major focus for human evolutionary studies. It has been argued that the procurement of small, difficult-to-catch, agile prey is a hallmark of complex behavior unique to our species; however, most research in this regard has been limited to the last 20,000 years in Europe and the Levant. Here, we present detailed faunal assemblage and taphonomic data from Fa-Hien Lena Cave in Sri Lanka that demonstrates specialized, sophisticated hunting of semi-arboreal and arboreal monkey and squirrel populations from ca. 45,000 years ago, in a tropical rainforest environment. Facilitated by complex osseous and microlithic technologies, we argue these data highlight that the early capture of small, elusive mammals was part of the plastic behavior of Homo sapiens that allowed it to rapidly colonize a series of extreme environments that were apparently untouched by its hominin relatives.