(1) Background: This study aims to investigate the association between different levels of physical activity (PAL) and health-related quality of life (HRQoL) in a random sample of the adult population; (2) Methods: The study material comprised 1100 adults of the city of Brasov, Romania (700 men, 400 women), aged 30-45 years old. We used the short version of the International Physical Activity Questionnaire Short Form (IPAQ-SF) and Short-Form Health Survey (SF-36) to assess PAL and HRQoL, respectively; (3) Results: The differences in the number of respondents in groups assessing their HRQoL differently and PA were statistically significant (p < 0.001), both among men and women. The PAL was shown to be positively correlated with the adult HROoL domains; (4) Conclusions: Our results confirm that the highest PAL values were associated with more favorable scores in HRQoL dimensions among the adult population.