Background Adult education institutions have been identified as potential settings to improve health literacy and address the health inequalities that stem from limited health literacy. However, few health literacy interventions have been tested in this setting. Methods Feasibility study for an RCT of the UK Skilled for Health Program adapted for implementation in Australian adult education settings. Implementation at two sites with mixed methods evaluation to examine feasibility, test for change in participants' health literacy and pilot test health literacy measures. Results Twenty-two socially disadvantaged adults with low literacy participated in the program and received 80-90 hours of health literacy instruction. The program received institutional support from Australia's largest provider of vocational education and training and was feasible to implement (100 % participation; >90 % completion; high teacher satisfaction). Quantitative results showed improvements in participants' health literacy skills and confidence, with no change on a generic measure of health literacy. Qualitative analysis identified positive student and teacher engagement with course content and self-reported improvements in health knowledge, attitudes, and communication with healthcare professionals. Conclusions Positive feasibility results support a larger RCT of the health literacy program. However, there is a need to identify better, multi-dimensional measures of health literacy in order to be able to quantify change in a larger trial. This feasibility study represents the first step in providing the high quality evidence needed to understand the way in which health literacy can be improved and health inequalities reduced through Australian adult education programs.