Background: Although physical activity (PA) has long been associated with cardiovascular disease (CVD), assessment of PA status has never been used as a part of CVD risk prediction tools. The aim of the present work was to examine whether the inclusion of PA status in a CVD risk model improves its predictive accuracy. Methods: Data from the 10-year follow-up (2002–2012) of the n = 2020 participants (aged 18–89 years) of the ATTICA prospective study were used to test the research hypothesis. The HellenicSCORE (that incorporates age, sex, smoking, total cholesterol, and systolic blood pressure levels) was calculated to estimate the baseline 10-year CVD risk; assessment of PA status was based on the International Physical Activity Questionnaire. The estimated CVD risk was tested against the observed 10-year incidence (i.e., development of acute coronary syndromes, stroke, or other CVD according to the World Health Organization [WHO]-International Classification of Diseases [ICD]-10 criteria). Changes in the predictive ability of the nested CVD risk model that contained the HellenicSCORE plus PA assessment were evaluated using Harrell’s C and net reclassification index. Results: Both HellenicSCORE and PA status were predictors of future CVD events (P < 0.05). However, the estimating classification bias of the model that included only the HellenicSCORE was significantly reduced when PA assessment was included (Harrel’s C = 0.012, P = 0.032); this reduction remained significant even when adjusted for diabetes mellitus and dietary habits (P < 0.05). Conclusions: CVD risk scores seem to be more accurate by incorporating individuals’ PA status; thus, may be more effective tools in primary prevention by efficiently allocating CVD candidates.