Objective: To assess the maximally achievable computed tomography (CT) dose reduction for coronary artery calcium (CAC) scoring with iterative reconstruction (IR) by using phantom-experiments and a systematical within-patient study. Methods: Our local institutional review-board approved this study and informed consent was obtained from all participants. A phantom and patient study were conducted with 30 patients (23 men, median age 55.0 (52.0-56.0) years) who underwent 256-slice electrocardiogram-triggered CAC-scoring at four dose levels (routine, 60%, 40%, and 20%-dose) in a single session. Tube-voltage was 120 kVp, tube-current was lowered to achieve stated dose levels. Data were reconstructed with filtered back-projection (FBP) and three IR levels. Agatston, volume and mass scores were determined with validated software and compared using Wilcoxon signed ranks-tests. Subsequently, patient reclassification was analyzed. Results: The phantom study showed that Agatston scores remained nearly stable with FBP between routine-dose and 40%-dose and increased substantially at lower dose. Twenty-three patients (77%) had coronary calcifications. For Agatston scoring, one 40%-dose and six 20%-dose FBP reconstructions were not interpretable due to noise. In contrast, with IR all reconstructions were interpretable. Median Agatston scores increased with FBP from 26.1 (5.2-192.2) at routine-dose to 60.5 (11.6-251.7) at 20% dose. However, IR lowered Agatston scores to 22.9 (5.9-195.5) at 20%-dose and strong IR (level 7) with Agatston reclassifications in 15%. Conclusion: IR allows for CAC-scoring radiation dose reductions of up to 80% resulting in effective doses between 0.15 and 0.18 mSv. At these dose-levels, reclassification-rates remain within 15% if the highest IR-level is applied.