Conflicting findings remain regarding associations between lifestyle behaviors and coronary artery calcium (CAC). We investigated concomitant associations of healthy food intake and cardiorespiratory fitness (CRF) with CAC. Data from 706 men and women 50 to 64 years old from the Swedish SCAPIS pilot trial were analyzed. A CAC score was calculated using the Agatston method. A Healthy Food Index (HFI) was established using data from a web-based food frequency questionnaire. CRF was assessed from a bike exercise test. Regression analyses were performed with occurrence of CAC (dichotomous) and level of CAC score in patients with CAC (continuous) as outcomes. 58% had 0 CAC score. HFI was significantly associated with having no CAC (standardized coefficient β = 0.18, p <0.001) but not with level of CAC score (β = -0.09, p = 0.34). CRF showed no significant association with having no CAC (β = -0.08, p = 0.12) or with the level of CAC score (β = -0.04, p = 0.64). However, there was an interaction between HFI and CRF (β = -0.23, p = 0.02); for increasing levels of CRF there was stronger negative association between HFI and level of CAC score, reaching β = -0.48, p = 0.045 for the highest CRF level. In conclusion, these results emphasize the importance of a healthy food intake in combination with higher CRF to counteract CAC development.