Elevated alcohol use disorders have been observed in 1991 Gulf War veterans from a variety of countries. This study used a self-report instrument, the Alcohol Use Disorders Identification Test (AUDIT), to ascertain whether any subgroups of 1232 male Royal Australian Navy (RAN) Gulf War veterans were at higher risk of hazardous or harmful alcohol use. Recursive partitioning/classification and regression tree (CART) analysis, followed by logistic regression, found five subgroups among the veterans, with differing risks of AUDIT caseness. The highest risk subgroup comprised current smokers. The other two high risk groups both consisted of former or never smokers of lower rank who were (1) not married, or (2) married, with a current diagnosis of major depression. The above subgroups were over three times as likely to exhibit AUDIT caseness than those who were former or never smokers of higher rank. The findings have important implications for effective development of public health initiatives designed to encourage safe alcohol use among veterans.