Objective: The primary aim was to analyze the association of moderate-to-vigorous physical activity (MVPA) with menopause symptomatology and its overall impact. A secondary/exploratory aim was to assess the association of different components of physical fitness with menopause symptomatology. Methods: This cross-sectional study comprised 191 perimenopausal women from Southern Spain (age range 45–60 years, mean age 52.6 ± 4.5 years). The Blatt–Kupperman Menopausal Index was used to evaluate menopause symptomatology. Objectively measured MVPA was registered with accelerometry. Physical fitness was assessed with the Senior Fitness Test battery plus handgrip strength and sit-and-reach tests. Results: After adjustment for multiple confounders, MVPA was only inversely associated with vertigo (r = −0.185, p < 0.05) and palpitations (r = −0.148, p < 0.05). Upper-body flexibility was inversely associated with the Blatt–Kupperman Menopausal Index global score (r = −0.147, p < 0.05). This test was also inversely associated with vertigo (r = −0.230, p < 0.01) and arthralgia (r = −0.168, p < 0.05). Lower-body muscle strength was associated with lower nervousness (r = −0.171, p < 0.05). Cardiorespiratory fitness was inversely associated with paresthesia (r = −0.158, p < 0.05), vertigo (r = −0.219, p < 0.01), fatigue (r = −0.159, p < 0.05) and arthralgia (r = −0.180, p < 0.05). Conclusion: The main findings of the present study indicate a weak association of objectively measured MVPA with menopause symptomatology. Exploratory analyses suggest that upper-body flexibility was associated with slightly lower overall menopause impact whereas neither MVPA nor any physical fitness components studied were associated with vasomotor symptoms.