The growing popularity of physical activity (PA) applications (apps) in recent years and the vast amounts of data that they generate present attractive possibilities for surveillance. However, measurement accuracy is indispensable when tracking PA variables to provide meaningful measures of PA. The purpose of this study was to examine the steps and distance criterion validity of freeware accelerometer-based PA smartphone apps, during incremental-intensity treadmill walking and jogging. Thirty healthy adults (25.9 ± 5.7 years) participated in this cross-sectional study. They were fitted with two smartphones (one with Android and one with iOS operating systems), each one simultaneously running four different apps (i.e., Runtastic Pedometer, Accupedo, Pacer, and Argus). They walked and jogged for 5 min at each of the predefined speeds of 4.8, 6.0, and 8.4 km/h on a treadmill, and two researchers counted every step taken during trials with a digital tally counter. Validity was evaluated by comparing each app with the criterion measure using repeated-measures analysis of variance (ANOVA), mean absolute percentage errors (MAPEs), and Bland–Altman plots. For step count, Android apps performed slightly more accurately that iOS apps; nevertheless, MAPEs were generally low for all apps (<5%) and accuracy increased at higher speeds. On the other hand, errors were significantly higher for distance estimation (>10%). The findings suggest that accelerometer-based apps are accurate tools for counting steps during treadmill walking and jogging and could be considered suitable for use as an outcome measure within a clinical trial. However, none of the examined apps was suitable for measuring distance.