This is one of the first studies to explore known preventive behaviours for type 2 diabetes (T2DM) among women with recent gestational diabetes (GDM), and the first to do so in a representative population sample. The aim of this study was to describe the prevalence of health-enhancing physical activity (PA) and explore its association with psychosocial and sociodemographic factors, in postnatal women with recent GDM. Cross-sectional telephone surveys were conducted among Queensland women with a recent history (≥6 months and ≤3 years since diagnosis) of GDM (N = 331), which included measures on PA behaviour, social support and self-efficacy for regular PA. The prevalence of health-enhancing PA among women with recent GDM was 37.2%. In multivariate analysis, both social support (OR = 1.06, 95% CI 1.03-1.09) and self-efficacy (OR = 1.04, 95% CI 1.004-1.07) were significantly associated with health-enhancing PA. The findings from this study demonstrate the need for postnatal follow-up to increase PA levels in women with recent GDM as this may reduce the risk of developing type 2 diabetes (T2DM) in this at-risk population. Strategies that address social support and self-efficacy for PA may be effective in increasing health-enhancing PA among women with recent GDM.