Background and objective The majority of Australians use complementary and alternative medicine (CAM). Despite concerns about safety, patterns of health literacy and CAM use in Australian general practice are unknown. Methods Pre-existing questionnaires assessing health literacy and CAM use (HLQ and I-CAM-Q) were distributed by eight practices across four Australian states to 800 patients aged 18 years and older for self-completion. Regression modelling and cluster analysis were applied to the data. Results The response rate was 47% (n = 374), the mean age was 53 years and 68% of participants were female. Two-thirds of participants used some form of CAM in the previous 12 months, and 60% believed CAM aided wellbeing. There were significant associations between cluster membership, education, sex and CAM use. Discussion Our findings suggest CAM use is a complex phenomenon, associated with gender and education. We demonstrated a cluster of female patients with high CAM use and lower health literacy warranting further research.