Aims: Exercise is increasingly being studied as treatment for alcohol use disorder (AUD). We examined the effects of an acute bout of exercise on alcohol craving, heterogeneity of response, and factors associated with reductions in craving. Methods: Within the context of a randomized controlled trial, we conducted an exploratory, single-arm study. In total, 117 adults with AUD (52.7 years; SD = 12.3; 68.4% female) and indications of alcohol craving (Desire for Alcohol Questionnaire, DAQ-short version total score >8) were included. The intervention was a 12-min submaximal fitness test performed on a cycle ergometer. We examined changes in participant's self-rated desire for alcohol immediately before and after exercise. Personal, clinical, and exercise-related factors associated with reductions (>0.5 SD) in craving were identified using hierarchical logistic regression. Results: In the total sample craving reduced from pre-to post-exercise (p < 0.001, g = 0.60 [0.40-0.79]). Three groups were observed: those whose craving decreased (70.1%; p < 0.001, g = 1.12 [0.85-1.40]), increased (16.2%; p < 0.001, g = 1.08 [0.51-1.64]), or did not change (13.7%). Forty percent experienced clinically meaningful reductions in craving (>0.5 SD). In fully adjusted models, two factors were associated with these reductions: higher pre-exercise cravings (OR = 1.15 [1.07-1.23], p < 0.001) and lower cardiorespiratory fitness (OR = 0.88 [0.79-1.00], p = 0.043). Conclusions: In most adults with AUD, short bouts of moderately intense aerobic exercise helps reduce cravings for alcohol. Those with higher cravings and lower cardiorespiratory fitness are most likely to benefit.