Phenotypic variation in natural populations is crucial for rapid adjustment to challenging environmental conditions such as exposure to heavy metal pollution. Hence, the study of variation in traits related to plant response to heavy metal stress provides valuable insight into the likelihood of a population’s survival. We investigate the patterns and mechanisms of intraspecific phenotypic variation for heavy metal accumulation and tolerance in bryophytes, one of the most resilient yet relatively understudied taxa. Two terrestrial mosses exposed to Cd and Cu in the laboratory, the heavy metal specialist Scopelophila cataractae and the facultative metallophyte Ceratodon purpureus, showed intraspecific differences in tolerance to these metals. Only the heavy metal specialist showed differences in accumulation which in the case of Cu could be associated to preferential relocation towards the stem to protect their main photosynthetic organs. We also report the first evidence for sexual dimorphism for Cd tolerance in C. purpureus (females being more tolerant than males). Our results provide support for high variation in the capacity of bryophytes to respond to environmental challenge despite potentially low levels of genetic variation and lack of previous exposure to stress, as well as evidence for metal-dependent, sex-specific differences in heavy metal tolerance in bryophytes.