The aim of this study was to estimate the genetic parameters of somatic cell count (SCC) and its relationship with production traits in the first three parities in Iranian Holstein dairy cows. Data were 1,891,559 test-day records of SCC, milk yield, and milk compositions on 276,217 lactations on 147,278 cows distributed in 134 herds. The number of test-day records in the first, second and third parities were 995,788 (on 147,278 cows), 593,848 (on 85,153 cows), and 301,923 (on 43,786 cows), respectively. Test-day SCCs were transformed to somatic cell scores (SCS). A random regression test-day animal model through four-trait three-lactation was used to estimate variance components for test-day records of SCS and lactation traits were included. Gibbs sampling was used to obtain marginal posterior distributions for the various parameters using a single chain of 200,000 iterates in which the first 50,000 iterates of each chain were regarded as a burn-in period. The mean heritability estimates for SCS (0.15 to 0.18) were lower than those for milk yield (0.36 to 0.38), fat yield (0.30 to 0.31), protein yield (0.31 to 0.32), fat percentage (0.21 to 0.25), and protein percentage (0.21 to 0.22). Low negative genetic correlations ranging from −0.05 to −0.30 were found between SCS and yield traits (milk, fat, and protein yields). The genetic correlation found between SCS and fat percentage was close to zero, however, a low positive genetic correlation ranging from 0.12 to 0.17 was found between SCS and protein percentage. Based on the results, it can be concluded that genetic selection for decreasing SCS would also increase lactation yield. The estimates found in this study can be used to perform breeding value estimations for national genetic evaluations in Iranian Holsteins using a multiple-trait, multiple-lactation random regression model.