Faunistic studies in sublittoral and littoral marine habitats on the Cape Peninsula, South Africa, have yielded three new species belonging to the genus Heteromysis, subgenus Heteromysis: H. cancellisp. n. associated with the diogenid hermit crab Cancellus macrothrix Stebbing, 1924, and H. fosterisp. n. extracted from 'empty' urchin and gastropod shells. The first documented mysid-cephalopod association is reported for H. octopodissp. n. which was found in dens occupied by Octopus vulgaris Cuvier, 1797, but was also captured from tide pools. The three new species differ from previously known E. Atlantic species, among other characters, by a single spine on the endopods of uropods in combination with large cornea and absence of median sternal processes on thoracic somites. They are also characterized by a white stripe along the dorso-lateral terminal margin of the eyestalks in living specimens. The new species appear quite similar to each other, but are distinguished by different depths of the telson cleft, different distributions of spines on the lateral margins of the telson, different numbers of segments on thoracic endopod 4, and by differently modified setae on the carpus of the third thoracic endopod, as well as on the carpopropodus of the fourth endopod. An updated key to the species of Heteromysis known from the E. Atlantic is given.