Abstract. – Shrimp are found in association with many hosts (sponges, anthozoans, mollusks, echinoids, ascidians and fish). Shrimp are rarely observed in association with jellyfish. The interaction between the cleaner shrimp Periclimenes paivai and jellyfish is poorly known, with only one published report for Brazilian waters. We add new information about this association, based on field and laboratory observations. Shrimp were collected from three locations on the coast of São Paulo State (Cananéia, Santos and São Sebastião) and from two species of scyphozoan medusae: Chrysaora lactea and Lychnorhiza lucerna. We classify the association as facultative commensalism, since the shrimp gain protection and probably feed on mucus produced by the jellyfish. The maximum carapace length of the shrimp collected was 9.2 mm. Medusa bell diameter ranged between about 10 and 19 cm for C. lactea and between 4.5 and 25 cm for L. lucerna. We also provide a list of records of Periclimenes in association with different scyphomedusae, and additional information on the size and coloration of P. paivai.