Changes in gene regulation are thought to underlie most phenotypic differences between species. For subterranean rodents such as the naked mole-rat, proposed phenotypic adaptations include hypoxia tolerance, metabolic changes, and cancer resistance. However, it is largely unknown what regulatory changes may associate with these phenotypic traits, and whether these are unique to the naked mole-rat, the mole-rat clade, or are also present in other mammals. Here, we investigate regulatory evolution in the heart and liver from two African mole-rat species and two rodent outgroups using genome-wide epigenomic profiling. First, we adapted and applied a phylogenetic modeling approach to quantitatively compare epigenomic signals at orthologous regulatory elements and identified thousands of promoter and enhancer regions with differential epigenomic activity in mole-rats. These elements associate with known mole-rat adaptations in metabolic and functional pathways and suggest candidate genetic loci that may underlie mole-rat innovations. Second, we evaluated ancestral and species-specific regulatory changes in the study phylogeny and report several candidate pathways experiencing stepwise remodeling during the evolution of mole-rats, such as the insulin and hypoxia response pathways. Third, we report nonorthologous regulatory elements overlap with lineage-specific repetitive elements and appear to modify metabolic pathways by rewiring of HNF4 and RAR/RXR transcription factor binding sites in mole-rats. These comparative analyses reveal how mole-rat regulatory evolution informs previously reported phenotypic adaptations. Moreover, the phylogenetic modeling framework we propose here improves upon the state of the art by addressing known limitations of inter-species comparisons of epigenomic profiles and has broad implications in the field of comparative functional genomics.