Background: Executive functions may underpin performance in live-fire tasks, whereas evidence for global physical fitness is mixed. We quantified the associations between cognitive flexibility (CF), inhibitory control (IC), overall physical fitness, and rifle marksmanship in cadets, and derived a parsimonious predictive model. Methods: Twenty second-year male airborne cadets (mean age 21.7 ± 2.2 years) completed a live-fire Basic Rifle Marksmanship (BRM) qualification (40 targets at 50–300 m); the Color Trails Test (CTT-1 and CTT-2; interference index) to index CF and processing speed; a stop-signal–style task (CogniFit) to assess IC indexed by NO-GO accuracy and GO-trial response time; and the Army Combat Fitness Test (ACFT). Associations were examined with Spearman correlations. Multiple linear regression with backward elimination and Bayesian model comparison evaluated predictive models. Results: Faster CTT-2 performance was associated with higher BRM scores (ρ = −0.48, p = 0.032), with a similar association for CTT-1 (ρ = −0.46, p = 0.042). The best-fitting regression model included CTT-2 time and IC–accuracy (adjusted R² = 0.345; RMSE = 7.03), with CTT-2 time the only significant predictor of BRM (b = −0.330, p = 0.006). Bayesian model comparison independently favored a parsimonious CTT-2–only model (P(M|data) = 0.222; BF_M = 5.41; BF₁₀ = 1.00; R² = 0.352). ACFT scores were not significantly associated with BRM. Conclusions: CF and processing speed are key correlates of live–fire rifle marksmanship in cadets, suggesting value in integrating executive–function elements into marksmanship training. Replication in larger cohorts is warranted.