Dietary patterns influence gut microbiota composition. To date, there has not been an assessment of diet and gut microbiota in Veterans, who have a history of unique environmental exposures, including military deployment, that may influence associations between diet and gut microbiota. Our aim was to characterise Veteran habitual dietary intake and quality, and to evaluate correlations between diet and gut microbiota. We administered Food Frequency Questionnaires (FFQs) and collected stool samples from 330 Veterans. FFQ data were used to generate Healthy Eating Indices (HEI) of dietary quality. Exploratory factor analysis was used to identify two dietary patterns we defined as "Western" and "Prudent." Stool samples underwent 16S rRNA gene sequencing, and the resulting data were used to evaluate associations with dietary variables/indices. Analyses included linear regression of α-diversity, constrained analysis of principal coordinates of β-diversity, and multivariate association with linear models and Analysis of Composition of Microbiomes analyses of dietary factors and phylum- and genus-level taxa. There were no significant associations between dietary patterns or factors and α- or β-diversity. At the phylum level, increasing HEI scores were inversely associated with relative abundance of Actinobacteria, and added sugar was inversely associated with abundance of Verrucomicrobia. Veterans largely consumed a Western-style diet, characterised by poor adherence to nutritional guidelines.