Background: Incidence and prevalence of cardiovascular disease (CVD) differ between sexes, and women experience CVD later than men. Changes in fibrin clot lysability are associated with CVD, and the present study addresses sex differences in fibrin clot lysability in asymptomatic middle-aged individuals and the relation to coronary artery calcification (CAC). Methods: Participants free of morbidities and medication, N = 163, were randomly chosen from a national registry among citizens, 50 or 60 years of age, and were followed for 5 years. CAC was determined by the Agatston (Ag) score both at baseline and at follow-up. Based on the changes in Ag, the population was divided into two groups: ΔAg = 0 U or ΔAg > 0 U. Fibrin clot analyses were based on turbidimetric methods. Results: At baseline, 116 women and 97 men were included; 84 women and 79 men completed the 5-year follow-up (77%). Independently of covariates, women with ΔAg > 0 had reduced mean (SD) fibrin lysability at follow-up, 40.2% (15.9), both in comparison to baseline, 47.8% (20.4), p = 0.001, to women with ΔAg = 0 U, 51.2% (24.5), p = 0.028, and to men with ΔAg > 0 U, 54.4% (21.0), p = 0.002. Conclusions: Fibrin clot lysability changes over time with considerable sex differences. Women with progression of CAC have reduced fibrin clot lysability compared to men, indicating a sex-specific association between morphological vessel wall changes and fibrin clot lysability.