Obesity is a major health problem, and although caloric restriction and exercise are successful strategies to lose adipose tissue in obese individuals, a simultaneous decrease in skeletal muscle mass, negatively effects metabolism and muscle function. To deeper understand molecular events occurring in muscle during weight-loss, we measured the expressional change in human skeletal muscle following a combination of severe caloric restriction and exercise over 4 days in 15 Swedish men. Key metabolic genes were regulated after the intervention, indicating a shift from carbohydrate to fat metabolism. Nicotinamide N-methyltransferase (NNMT) was the most consistently upregulated gene following the energy-deficit exercise. Circulating levels of N1-methylnicotinamide (MNA), the product of NNMT activity, were doubled after the intervention. The fasting-fed state was an important determinant of plasma MNA levels, peaking at ~18 h of fasting and being lowest ~3 h after a meal. In culture, MNA was secreted by isolated human myotubes and stimulated lipolysis directly, with no effect on glucagon or insulin secretion. We propose that MNA is a novel myokine that enhances the utilization of energy stores in response to low muscle energy availability. Future research should focus on applying MNA as a biomarker to identify individuals with metabolic disturbances at an early stage.