Background: Physical literacy (PL), given as a multidimensional construct, is considered a person's capacity and commitment to a physically active lifestyle. We investigated the effect of a holistic physical exercise training on PL among physically inactive adults. Methods: A non-randomised controlled study was conducted. Thirty-one physically inactive adults in the intervention group (IG; 81% females, 44 ± 16 years) participated in a holistic physical exercise training intervention once weekly for 15 weeks. A matched, non-exercising control group (CG) consisted of 30 physically inactive adults (80% female, 45 ± 11 years). PL, compliance and sociodemographic parameters were measured. PL was evaluated by a questionnaire, covering five domains: physical activity behaviour, attitude towards a physically active lifestyle, exercise motivation, knowledge and self-confidence/self-efficacy. Data were analysed using ANCOVA models, adjusted for age, gender and BMI at baseline. Results: At post-training intervention, the IG showed significant improvements in PL (p = 0.001) and in the domains physical activity behaviour (p = 0.02) and exercise self-confidence/self-efficacy (p = 0.001), with no changes overserved for the CG regarding PL and those domains. No intervention effect were found for the other three domains, i.e. attitude, knowledge and motivation. Additionally, for the IG baseline BMI was identified to be positively correlated with physical exercise-induced improvements in PL (β = 0.51, p = 0.01). Conclusions: The results from this study are very useful for further public health activities, which aim at helping physically inactive adults to adopt a physically active lifestyle as well as for the development of further PL intervention strategies. This pilot-study was a first attempt to measure PL in inactive adults. Yet, a validated measurement tool is still not available. Further research is necessary to determine the psychometric properties for this PL questionnaire. Trial registration: German Clinical Trials Register (DRKS), DRKS00013991, date of registration: 09.02.2018, retrospectively registered.