In a previous study, the whole transcriptome of the vastus lateralis muscle from sedentary elderly and from age-matched athletes with an exceptional record of high-intensity, life-long exercise training was compared—the two groups representing the two extremes on a physical activity scale. Exercise training enabled the skeletal muscle to counteract age-related sarcopenia by inducing a wide range of adaptations, sustained by the expression of protein-coding genes involved in energy handling, proteostasis, cytoskeletal organization, inflammation control, and cellular senescence. Building on the previous study, we examined here the network of non-coding RNAs participating in the orchestration of gene expression and identified differentially expressed micro- and long-non-coding RNAs and some of their possible targets and roles. Unsupervised hierarchical clustering analyses of all non-coding RNAs were able to discriminate between sedentary and trained individuals, regardless of the exercise typology. Validated targets of differentially expressed miRNA were grouped by KEGG analysis, which pointed to functional areas involved in cell cycle, cytoskeletal control, longevity, and many signaling pathways, including AMP-activated protein kinase (AMPK) and mammalian target of rapamycin (mTOR), which had been shown to be pivotal in the modulation of the effects of high-intensity, life-long exercise training. The analysis of differentially expressed long-non-coding RNAs identified transcriptional networks, involving lncRNAs, miRNAs and mRNAs, affecting processes in line with the beneficial role of exercise training.