Purpose: Olive oil, being rich in mono-unsaturated fatty acids and anti-inflammatory compounds, may have protective effects against cardiovascular disease (CVD). The aim of the present work was to examine the association of olive oil consumption with the 10-year CVD incidence in adults without pre-existing CVD. Methods: The ATTICA Study is a prospective, population-based study conducted in the greater metropolitan area of Athens (Attica, Greece). During 2001–2002, 3042 CVD-free adults (1514 men and 1528 women) were voluntarily recruited to the ATTICA study. Among various dietary habits, consumption of olive oil and other fats/oils was assessed at baseline; participants were classified into three groups (no use; mixed use; and exclusive use of olive oil). In 2011–2012, the 10-year study follow-up was performed, recording the fatal/non-fatal CVD incidence in 2020 participants (mean follow-up duration: 8.41 years). Results: After controlling for various covariates, an inverse association between exclusive olive oil use and the risk of developing CVD was observed (relative risk 0.07, 95% CI: 0.01–0.66) compared to those not consuming olive oil. Further adjustment for fibrinogen plasma levels (among various inflammatory markers) showed a significant mediation effect on the previous association. Conclusions: These findings support exclusive olive oil consumption, a key component of the Mediterranean diet, for the primary CVD prevention, in adults without pre-existing disease. Circulating fibrinogen levels appear to play a mediating role in this relationship.