Background: Growing evidence suggests that physical exercise (EX) may reduce mortality and recurrence risk in patients (pts) with cancer, as well as help in managing cancer treatment side effects and improve quality of life (QoL). Despite these well-recognized benefits, most pts are insufficiently active, and compliance with the EX intervention is often challenging. This pilot study aimed to evaluate the safety, feasibility, and preliminary efficacy of a 3-month EX-intervention in pts with cancer. Methods: A pilot, two-center randomized controlled trial was conducted on pts with different cancers at early stages. Pts allocated in the 3-month EX intervention participated in bi-weekly aerobic and resistance training tailored to the patient's baseline condition and preferences. The duration of aerobic training progressively increased over weeks, whereas the resistance component consisted of body weight or elastic-bands exercises performed in 2-3 sets of 8-12 repetitions. EX intensity was moderate and monitored using the 10-point Borg Rating of the Perceived Exertion Scale. Pts randomized to control received usual care. Primary study endpoints were safety, monitored through the Common Terminology Criteria for Adverse Events (AEs), and feasibility, evaluated through recruitment rate, adherence, and withdrawals. Secondary endpoints included functional capacity, using the Six minutes walking test, and muscle strength, with the handgrip and leg press test. European Organization for Research and Treatment of Cancer Quality of Life and Core Questionnaire (EORTC- QLQ-C30) was used to assess the QoL. Descriptive statistics was applied, and repeated-measures analysis of variance was used to evaluate within- and between-group differences. Results: With a 38% recruitment rate, 57 pts were randomized (56 years; 68% breast, 14% colorectal) to the EX-intervention (n = 37) and controls (n = 20). Five dropouts occurred, n = 3 in the EX-group (leukemia onset n = 1, psychiatric disorder n = 1, gonarthrosis n = 1), and n = 2 in the controls (lack of interest n = 2). Adherence to EX-sessions was high, 93%. Concerning safety, three AEs were reported: worsening in the lymphedema, Grade 1 (n = 2), and elbow inflammation, Grade 1. Compared to the controls, EX-group reported a significant increase in functional capacity (within group, p < 0.01), and lower limb strength (within and between group, p < 0.01). Regarding QoL, EX produced enhancements in social function (within group, p < 0.05), fatigue (within group, p < 0.05), nausea and vomiting (within group p < 0.01), dyspnea (within group, p < 0.05), insomnia (within group, p < 0.05), and loss of appetite (within group, p < 0.01). Conclusions: Preliminary findings support the feasibility of a combined aerobic and resistance EX in pts with cancer with minimal AEs. Moreover, improvements in physical parameters and some domains of QoL were detected. Clinical trial information: NCT04226508.