Background: Wasting of body mass and skeletal muscle frequently develops in patients with cancer and is associated with impaired functional ability and poor clinical outcome and quality of life. This study aimed to evaluate the feasibility and explore the effect of a multimodal intervention targeting nutritional status in patients with non-small cell lung cancer receiving primary anti-neoplastic treatment. Additionally, predictive and prognostic factors of gaining skeletal muscle were explored. Methods: This was a single-centre multimodal intervention trial using a historical control group. The multimodal intervention involved fish oil intake (2 g of eicosapentaenoic acid or docosahexaenoic acid daily), regular dietary counselling and unsupervised physical exercise twice weekly during the first three cycles of primary anti-neoplastic treatment. Feasibility was assessed through recruitment rate, completion rate and compliance rate with the intervention. Differences in skeletal muscle, body weight, and physical function between the intervention and historical control groups were analysed. Factors contributing to increased skeletal muscle were explored using univariate and multivariate ordinal logistic regression analyses. Results: The recruitment and completion rates were 0.48 (n = 59/123) and 0.80 (n = 46/59), respectively. The overall compliance rate with all five individual interventions was 0.60 (n = 28/47). The individual compliance rates were 0.81 (n = 38/47) with fish oil intake, 0.94 (n = 44/47) with energy intake, 0.98 (n = 46/47) with protein intake, 0.51 (n = 24/47) with resistance exercise and 0.57 (n = 27/47) with aerobic exercise. No mean differences in skeletal muscle, body weight, or physical function were found between the intervention and control groups. However, a larger proportion of patients in the intervention group gained skeletal muscle (p < 0.02). The identified contributing factors of muscle gain were weight gain (OR, 1.3; p = 0.01), adherence to treatment plan (OR, 4.6; p = 0.02), stable/partial response (OR, 3.3; p = 0.04) and compliance to the intervention (OR, 7.4; p = 0.01). Age, sex, tumour stage, performance status, treatment type and baseline cachexia did not predict muscle gain. Conclusion: This three-dimensional intervention in patients with lung cancer undergoing primary anti-neoplastic treatment was feasible and increased the proportion of patients gaining skeletal muscle. Dietary counselling and fish oil use were useful strategies. The motivation for conducting unsupervised physical intervention was low. Clinical trials.gov identifier: NCT04161794.