In this paper, we describe worked and pigment-stained Nautilus shell artefacts recovered from Jerimalai, Timor-Leste. Two of these artefacts come from contexts dating to between 38,000 and 42,000 cal. BP (calibrated years before present), and exhibit manufacturing traces (drilling, pressure flaking, grinding), as well as red colourant staining. Through describing more complete Nautilus shell ornaments from younger levels from this same site (>15,900, 9500, and 5000 cal. BP), we demonstrate that those dating to the initial occupation period of Jerimalai are of anthropogenic origin. The identification of such early shell working examples of pelagic shell in Island Southeast Asia not only adds to our growing understanding of the importance of marine resources to the earliest modern human communities in this region, but also indicates that a remarkably enduring shell working tradition was enacted in this area of the globe. Additionally, these artefacts provide the first material culture evidence that the inhabitants of Jerimalai were not only exploiting coastal resources for their nutritional requirements, but also incorporating these materials into their social technologies, and by extension, their social systems. In other words, we argue that the people of Jerimalai were already practicing a developed coastal adaptation by at least 42,000 cal. BP.