Histone post-translational modifications (PTMs) are epigenetic marks that can be induced by environmental stress and elicit heritable patterns of gene expression. To investigate this process in an ecological context, we characterized the influence of salinity stress on histone PTMs within the gills, kidney, and testes of Mozambique tilapia (Oreochromis mossambicus). A total of 503 histone PTMs were quantified in each tissue sample and compared between freshwater-adapted fish exposed to salinity treatments that varied in intensity and duration. Three salinity-responsive histone PTMs were identified in this study. When freshwater-adapted fish were exposed to seawater for two hours, the relative abundance of H1K16ub significantly increased in the gills. Long-term salinity stress elicited changes in an additional two histone PTMs in the testes. When freshwater-adapted fish were exposed to a pulse of severe salinity stress, where salinity reached a maximum of 82.5 g/kg, the relative abundance of H3K14ac and H3K18ub decreased significantly in the testes. This study demonstrates that specific types of salinity stress can alter histone PTMs in Mozambique tilapia, both in an osmoregulatory organ and in the germ line. These results signify a potential for histone PTMs to be involved in salinity acclimation and adaptation in euryhaline fishes, thereby adding to a growing body of evidence that epigenetic mechanisms are involved in such processes.