Allium mongolicum Regel (A. mongolicum) is a perennial and xerophytic Liliaceous allium plant in high altitude desert steppe and desert areas. Feeding A. mongolicum greatly reduced unpleasant mutton flavor and improves meat quality of sheep. We analyzed epigenetic regulatory mechanisms of water extracts of A. mongolicum (WEA) on sheep muscle and adipose using RNA-Seq and whole-genome Bisulfite sequencing. Feeding WEA reduced differentially expressed genes and long non-coding RNAs (lncRNAs) between two tissues but increased differentially methylation regions (DMRs). LncRNA and DMR targets were both involved in ATP binding, ubiquitin, protein kinase binding, regulation of cell proliferation, and related signaling pathways, but not unsaturated fatty acids metabolism. Besides, tissue specific targets were involved in distinct functional annotations, e.g., Golgi membrane and endoplasmic reticulum for muscle lncRNA, oxidative phosphorylation metabolism for adipose lncRNA, dsRNA binding for muscle DMRs. Epigenetic regulatory networks were also discovered to discovered essential co-regulated modules, e.g., co-regulated insulin secretion module (PDPK1, ATP1A2, CACNA1S and CAMK2D) in adipose. The results indicated that WEA induced distinct epigenetic regulation on muscle and adipose to diminish transcriptome differences between tissues, which highlights biological functions of A. mongolicum, tissue similarity and specificity, as well as regulatory mechanism of mutton odor.