Bacterial microbiomes of cnidarians are being extensively studied. It has been shown that bacteria influence nutrition, life cycle regulation and health of their cnidarian hosts. They are also considered as a potential source of new biologically active substances. Some data on microbiomes are available for representatives of all cnidarian classes except Staurozoa, a poorly studied group of the marine stalked jellyfish. In this study we used a metagenomic approach to describe the bacterial microbiome of the staurozoan Haliclystus auricula from the Barents Sea. We showed the qualitative composition of the bacterial community associated with H. auricula and identified 18 core bacterial genera. Colwellia and Marinomonas were the dominant ones, with an average relative abundance of about 30% and 14%, respectively. The relative abundance of other bacteria was lower. Most of the core bacteria were psychrophilic or psychrotolerant. Some of them have previously be shown to be capable of complex polysaccharide degradation and antimicrobial compounds production. The comparison of the H. auricula bacterial microbiome with those of other studied cnidarian species revealed common features at high taxonomic levels but significant differences at the genus level. The most numerous bacterial genera were found in all cnidarian species involved in the analysis, but their relative abundance in H. auricula was unique. The microbiome of H. auricula appears to be heavily influenced by the cold waters of the Barents Sea, which may explain the differences from the microbiomes of cnidarians from warmer waters.