Background: The proteolytic enzymes involved in normal protein turnover in fish muscle are also responsible for post-mortem softening of the flesh and are therefore potential determinants of product quality. The main enzyme systems involved are calpains, cathepsins, and the ubiquitin-proteasome (UbP). In this study on Sparus aurata (Sa), the coding sequences of cathepsins (SaCTSB and SaCTSDb) and UbP family members (SaN3 and SaUb) were cloned from fast skeletal muscle, and their expression patterns were examined during ontogeny and in a fasting/re-feeding experiment. Results: The amino acid sequences identified shared 66-100% overall identity with their orthologues in other vertebrates, with well conserved characteristic functional domains and catalytic residues. SaCTSDb showed phylogenetic, sequence and tissue distribution differences with respect to its paralogue SaCTSDa, previously identified in the ovary. Expression of gilthead sea bream cathepsins (B, L, Da, Db) and UbP members (N3, Ub, MuRF1 and MAFbx) in fast skeletal muscle was determined at three different life-history stages and in response to fasting and re-feeding in juveniles. Most of the proteolytic genes analysed were significantly up-regulated during fasting, and down-regulated with re-feeding and, between the fingerling (15 g) and juvenile/adult stages (~50/500 g), consistent with a decrease in muscle proteolysis in both later contexts. In contrast, SaCTSDa and SaMuRF1 expression was relatively stable with ontogeny and SaUb had higher expression in fingerlings and adults than juveniles. Conclusions: The data obtained in the present study suggest that cathepsins and UbP genes in gilthead sea bream are co-ordinately regulated during ontogeny to control muscle growth, and indicate that feeding regimes can modulate their expression, providing a potential dietary method of influencing post-mortem fillet tenderisation, and hence, product quality.