Background: The impact of nutritional status and diet composition on mitochondrial oxidative phosphorylation (OXPHOS) in fish remains largely unknown. To identify biomarkers of interest in nutritional studies, herein we obtained a deep-coverage transcriptome by 454 pyrosequencing of liver and skeletal muscle cDNA normalised libraries from long-term starved gilthead sea bream (Sparus aurata) and fish fed different diets. Results: After clean-up of high-throughput deep sequencing reads, 699,991 and 555,031 high-quality reads allowed de novo assembly of liver and skeletal muscle sequences, respectively (average length: 374 and 441 bp; total megabases: 262 and 245 Mbp). An additional incremental assembly was completed by integrating data from both tissues (hybrid assembly). Assembly of hybrid, liver and skeletal muscle transcriptomes yielded, respectively, 19,530, 11,545 and 10,599 isotigs (average length: 1330, 1208 and 1390 bp, respectively) that were grouped into 15,954, 10,033 and 9189 isogroups. Following annotation, hybrid transcriptomic data were used to construct an oligonucleotide microarray to analyse nutritional regulation of the expression of 129 genes involved in OXPHOS in S. aurata. Starvation upregulated cytochrome c oxidase components and other key OXPHOS genes in the liver, which exhibited higher sensitive to food deprivation than the skeletal muscle. However, diet composition affected OXPHOS in the skeletal muscle to a greater extent than in the liver: most of genes upregulated under starvation presented higher expression among fish fed a high carbohydrate/low protein diet. Conclusions: Our findings indicate that the expression of coenzyme Q-binding protein (COQ10), cytochrome c oxidase subunit 6A2 (COX6A2) and ADP/ATP translocase 3 (SLC25A6) in the liver, and cytochrome c oxidase subunit 5B isoform 1 (COX5B1) in the liver and the skeletal muscle, are sensitive markers of the nutritional condition that may be relevant to assess the effect of changes in the feeding regime and diet composition on fish farming.