Background: Physical activity (PA) offers numerous benefits to health and well-being, but most adults are not sufficiently physically active to afford such benefits. The 10,000 steps campaign has been a popular and effective approach to promote PA. The Transtheoretical Model posits that individuals have varying levels of readiness for health behavior change, known as Stages of Change (Precontemplation, Contemplation, Preparation, Action, and Maintenance). Few validated assessment instruments are available for determining Stages of Change in relation to the PA goal of 10,000 steps per day. The purpose of this study was to assess the criterion-related validity of the SoC-Step, a brief 10,000 steps per day Stages of Change instrument. Methods: Participants were 504 Australian adults (176 males, 328 females, mean age = 50.8 ± 13.0 years) from the baseline sample of the Walk 2.0 randomized controlled trial. Measures included 7-day accelerometry (Actigraph GT3X), height, weight, and self-reported intention, self-efficacy, and SoC-Step: Stages of Change relative to achieving 10,000 steps per day. Kruskal-Wallis H tests with pairwise comparisons were used to determine whether participants differed by stage, according to steps per day, general health, body mass index, intention, and self-efficacy to achieve 10,000 steps per day. Binary logistic regression was used to test the hypothesis that participants in Maintenance or Action stages would have greater likelihood of meeting the 10,000 steps goal, in comparison to participants in the other three stages. Results: Consistent with study hypotheses, participants in Precontemplation had significantly lower intention scores than those in Contemplation (p = 0.003) or Preparation (p < 0.001). Participants in Action or Maintenance stages were more likely to achieve ≥10,000 steps per day (OR = 3.11; 95 % CI = 1.66,5.83) compared to those in Precontemplation, Contemplation, or Preparation. Intention (p < 0.001) and self-efficacy (p < 0.001) to achieve 10,000 steps daily differed by stage, and participants in the Maintenance stage had higher general health status and lower body mass index than those in Precontemplation, Contemplation and Preparation stages (p < 0.05). Conclusions: This brief SoC-Step instrument appears to have good criterion-related validity for determining Stages of Change related to the public health goal of 10,000 steps per day. Trial registration: Australian New Zealand Clinical Trials Registry reference: ACTRN12611000157976 World Health Organization Universal Trial Number: U111-1119-1755.