Background: Aboriginal and Torres Strait Islander women experience higher rates of heart disease and type 2 diabetes than non-Indigenous Australian women. Increasing physical activity, improving diets and losing weight have been shown to reduce cardio metabolic risk. The primary aim was to evaluate the effectiveness of a 12-week structured exercise and nutrition program in a cohort of urban Indigenous Australian women on waist circumference, weight and biomedical markers of metabolic functioning from baseline (T1) to program completion (T2). The secondary aim assessed whether these outcomes were maintained at 3-month follow-up. Methods. One hundred Aboriginal and/or Torres Strait Islander women aged 18-64 years living in the Adelaide metropolitan area were recruited. The program included two 60-minute group cardiovascular and resistance training classes per week, and four nutrition education workshops. Participants were randomly assigned to an 'active' group or 'waitlisted' control group. Body weight, height, waist and hip circumference, blood pressure, fasting glucose, fasting insulin, glycated haemoglobin (HbA1C), lipid profile and C-reactive protein (CRP) were assessed at baseline (T1), immediately after the program (T2) and three months post program (T3). Results: The active group showed modest reductions in weight and body mass index (BMI). Compared to the waitlisted group, the active group had a statistically significantly change in weight and BMI from baseline assessments; at T2, "1.65 kg and "0.66 kg/m2 and at T3, "2.50 kg and "1.03 kg/m2, respectively. Systolic and diastolic blood pressure also had a statistically significant difference from baseline in the active group compared to the waitlisted group at T2, "1.24 mmHg and "2.46 mmHg and at T3, "4.09 mmHg and "2.17 mmHg, respectively. The findings were independent of the baseline measure of the outcome variable, age, households with children and employment status. Changes in waist circumference and other clinical measures were not significant at T2 or T3. The primary outcome measure, waist circumference, proved problematic to assess reliably. Missing data and participants lost to follow-up were significant. Conclusions: This 12-week exercise program demonstrated modest reductions in weight, BMI and blood pressure at T2, which improved further at 3-month follow-up (T3). Positive intervention effects were observed despite low attendance at exercise classes. Structured exercise programs implemented in community settings require attention to understanding the barriers to participation for this high risk group. Trial registration. Australian New Zealand Clinical Trials Registry ACTRN12610000224022.