The microbiota associated with marine invertebrates is species- and location-specific and is greatly related to the health and survival of the host. The increasing interest in applying sea cucumbers as food, nutraceutical or pharmaceutical, lead to advancement in the biological research of potential or actual commercial species. In the case of cold-water sea cucumbers, they have important functions within ecosystems, and the associated microbiota could be key to aquaculture establishment or the synthesis of key bioactives and biopolymers. The red sea cucumber Parastichopus tremulus is a deposit-feeding species extracting nutrients from benthic sediments, and for this species the interactions with the surrounding microbial communities are largely unknown. In this study we have carried out isolation of the culturable microorganisms from 3 to 5 different points on the skin of 20 sea cucumber individuals from two different fjord locations in western Norway. The identification of purified microbial isolates was approached by biochemical and molecular methods (API test, MALDI-TOF, sequencing). The predominant number of isolates were obtained from Marine Agar and Sabouraud media and according to MALDI-TOF results belonged to Bacillaceae, Pseudomonadaceae, Lactic Acid Bacteria (LAB), Shewanellaceae, and various halotolerant and cryotolerant bacterial species. The API test system was not adequate, even with culture related adaptations, to the identification of the marine isolates. To the best of our knowledge this is the first report on compositional characterization of the associated skin microbiota of P. tremulus.