Worldwide, depressive disorder is one of the leading determinants of disability-adjusted life years. Although there are benefits associated with a higher physical activity (PA) level, there is a lack of information related to this relationship, especially in countries such as Czechia, where modern approaches to mental health care only recently emerged. The present study aimed to evaluate the association between the level of depression and different PA levels following the World Health Organization (WHO) PA guidelines and according to specific symptoms that indicate depression. Multivariable-adjusted Poisson regression models were used to calculate the prevalence rate (PR) in a sample of 2123 participants (45.3% men, median 48 years). Compared to subjects with insufficient PA, moderate and high PA levels were inversely associated with continuous depression scores (PR = 0.85; 95% CI: 0.75-0.97; and PR = 0.80; 95% CI: 0.70-0.92). Depressed mood and worthlessness were the symptoms associated with moderate and high PA. Tiredness, change in appetite, and concentration problems were related to high PA. The results suggest that reaching the minimum PA target according to the guidelines seems to be effective, and this could stimulate adherence. However, more specific improvements in symptomatology will require a subsequent gradual increase in PA levels.