The Mediterranean Sea is one of the world’s hotspots for marine bio-invasions. Most invasions are first documented based on an initial record of occasional adult captures. However, reports of larval stages could indicate that there is an adult population that is reproducing and therefore well established in the area. The spread of the oriental shrimp, Palaemon macrodactylus, from its native estuarine waters of southeast Asia to new regions worldwide is well documented. We report the first record of this species in the Mediterranean based on the presence of its larval stages in plankton samples. Decapod larvae were collected in five offshore plankton surveys performed off the Balearic Islands (western Mediterranean), and zoeae III and VI of the oriental shrimp werefound among them. Taking into account the duration of the successive developmental stages, and the hydrodynamic characteristics of the study area, these larvae were most probably spawned by adult populations not yet documented. The larvae were found in marine waters despite the fact that adults usually inhabit brackish waters. Our study is a good example of how plankton studies can help to detect larval stages of invasive species before the adult populations are detected.