Introduction: Military personnel require a high standard of health, nutrition, and physical fitness to perform their duties at optimal capacity. This study assessed the barriers and enablers for healthy eating in Australian Army (AA) personnel and identified their level of interest for future nutrition support. Methods: A convenience sample of AA completed a researcher-designed questionnaire assessing dietary, shopping and cooking practices, attitudes towards nutrition, barriers and enablers to healthy eating, and interest in future nutrition initiatives. Chi-square, logistic regression, and general linear models were used to evaluate associations between military roles, sex, and age. Data are reported as proportions (%) or mean ± SD. Results: Participants (n = 667; 91% male; 29.7 ± 9.2 years) reported lack of time (32.7%), motivation (23.7%), ease of access to take away foods (20.8%) and frequent field deployment (16.3%) as main factors challenging healthy eating. Approximately half (58.2%) of the sample reported receiving nutrition education during their military career. Key factors enabling healthy eating included the desire to improve health, physique (reduce fat and/or increase lean mass) and enhance job performance. Regarding interest in future nutrition initiatives, >50% of participants requested assistance to improve physique, general health, sports/physical performance, and dietary supplements as key elements. Face to face (60.3%) and electronic (Internet/smartphone) approaches (52.6%) to nutrition education were most popular. Conclusion: Time, motivation, deployment, and ready access to take away food challenged healthy eating in this AA sample. However, participants were keen to engage with nutrition education for physique improvement, military readiness, and health reasons.