This study aimed to determine the influence of arch stiffness on running spatiotemporal parameters at a common speed for a wide range of endurance runners (i.e., 12 km·h−1). In total, 97 runners, 52 men and 45 women, completed a treadmill running protocol at 12 km·h−1. Spatiotemporal parameters were measured using the OptoGait system, and foot structure was assessed by determining arch stiffness. Since between-sex differences were found in anthropometric and foot structure variables, data analysis was conducted separately for men and women, and body mass and height were considered as covariates. For both sexes, a k-means cluster analysis grouped participants according to arch stiffness, by obtaining a group of low-arch stiffness (LAS group) and a group of high-arch stiffness (HAS group), with significant differences in arch stiffness (p < 0.001, for both men and women). No significant differences between LAS and HAS groups were found in running spatiotemporal parameters, regardless of sex (p ≥ 0.05). For both sexes, the partial correlation analysis reported no significant correlations (p ≥ 0.05) between foot structure variables and running spatiotemporal parameters. The results obtained show no differences in spatiotemporal gait characteristics during running at submaximal velocity between runners with low-arch stiffness and those with high-arch stiffness, regardless of sex. These findings may have important implications for clinicians and coaches by adding more evidence to the debate about the use of static foot classification measures when characterizing the foot and its biomechanics during running.