Although mitochondrial dysfunction is implicated in the pathogenesis of obesity, the molecular mechanisms underlying obesity-related metabolic abnormalities are not well established. We performed mitochondrial quantitative proteomic and whole transcriptome analysis followed by functional annotations within liver and skeletal muscles, using fasted and non-fasted 16- and 48-week-old high-fat diet (HFD)-fed and normal diet-fed (control group) wild-type C56BL/6J mice, and hyperphagic ob/ob and db/db obese mice. Our study identified 1,675 and 704 mitochondria-associated proteins with at least two peptides in liver and muscle, respectively. Of these, 221 liver and 44 muscle proteins were differentially expressed (adjusted p values ≤ 0.05) between control and all obese mice, while overnight fasting altered expression of 107 liver and 35 muscle proteins. In the liver, we distinguished a network of 27 proteins exhibiting opposite direction of expression changes in HFD-fed and hyperphagic mice when compared to control. The network centered on cytochromes P450 3a11 (Cyp3a11) and 4a14 (Cyp4a14), and fructose-bisphosphate aldolase B (Aldob) proteins which bridged proteins cluster involved in Metabolism of xenobiotics with proteins engaged in Fatty acid metabolism and PPAR signaling pathways. Functional annotations revealed that most of the hepatic molecular alterations, which characterized both obesity and fasting, related to different aspects of energy metabolism (such as Fatty acid metabolism, Peroxisome, and PPAR signaling); however, only a limited number of functional annotations could be selected from skeletal muscle data sets. Thus, our comprehensive molecular overview revealed that both obesity and fasting states induce more pronounced mitochondrial proteome changes in the liver than in the muscles.