Background: In this study we analyzed the association between physical activity and sedentary lifestyle with vascular aging in Spanish populations aged 35–75 years. Methods: A cross-sectional study was developed, in which 501 subjects aged 35–75 years were recruited. Physical activity and sedentary time were measured with an accelerometer (Actigraph GTX3) for a week. We measured carotid–femoral pulse wave velocity (cfPWV) by a Sphygmo Cor® device and carotid intima-media thickness (cIMT) by ultrasound (Sonosite Micromax®). The vascular aging index (VAI) was calculated as described in the literature. Vascular aging was defined considering the 25th and 75th percentiles by age and sex of cfPWV and VAI, presence of vascular injury, type-2 diabetes mellitus or arterial hypertension. Individuals were classified into three groups: healthy, normal, and early vascular aging. Results: The mean age of the sample was 55.90 \pm 14.24 years, 50% being women. Total physical activity was negatively associated with cfPWV (\beta = –0.454) and VAI (\beta = –1.845). Similarly, the number of steps per day obtained a negative association with cfPWV (\beta = –0.052) and VAI (\beta = –0.216), while sedentary time showed a positive association with cfPWV (\beta = 0.028) and VAI (\beta = 0.117). In the analysis by sex, the results showed similar values. The odds ratio (OR) of total physical activity of subjects classified as early vascular aging (EVA) with regarding those classified as healthy vascular aging (HVA) was 0.521 (95% confidence interval [CI] 0.317 to 0.856) for cfPWV, and 0.565 (95% CI 0.324 to 0.986) for VAI. In terms of the number of steps per day, the OR was 0.931 (95% CI 0.875 to 0.992) for cfPWV and 0.916 (95% CI 0.847 to 0.990) for VAI and for sedentary time the OR was 1.042 (95% CI 1.011 to 1.073) for cfPWV and 1.037 (95% CI 1.003 to 1.072) for VAI. The OR of subjects classified as vigorous physical activity was 0.196 (95% CI 0.041 to 0.941) using cfPWV and 0.161 (95% CI 0.032 to 0.820) using VAI. In the analysis by sex, the results showed an association in men when cfPWV was used and an association in women when VAI was used to define vascular aging. Conclusions: The results of this study indicate that the more time spent performing physical activity and the less sedentary time, the lower the arterial stiffness and the probability of developing early vascular aging. Clinical Trial Registration: The study was registered in ClinicalTrials.gov (number: NCT02623894).