The main objective of this study was to estimate the genetic and phenotypic relationships between calving difficulty (CD) and fertility traits, including success at first service (SF), number of inseminations to conception (INS), interval from calving to first service (CTFS), interval between first and last service (IFL) and days open (DO), in first-parity Iranian Holsteins under standard (SMMs) and recursive (RMMs) mixed models. The data analysed in this paper included 29 950 records on CD and fertility traits, collected in the time period from 1995 to 2014 by the Animal Breeding and Improvement Center of Iran. Under all observed SMMs and RMMs, five bivariate sire-maternal grandsire models (ten bivariate analyses in total) were used for the analyses. Recursive models were applied with a view to consider that CD influences the fertility traits in the subsequent reproductive cycle and the genetic determination of CD and fertility traits by fitting CD as covariate for any of the fertility traits studied. The existence of such cause-and-effect is considered in RMMs but not in SMMs. Our results implied a statistically non-zero magnitude of the causal relationships between CD and all the fertility traits studied, with the former influencing the latter. The causal effects of CD on SF (on the observed scale, %), INS, CTFS, IFL and DO were −2.23%, 0.10 services, 1.93 days, 3.76 days and 5.61 days, respectively. Direct genetic correlations between CD and the fertility traits under both models were not statistically different from zero (95% HPD interval included zero), except for the correlation between CD and CTFS, which were 0.197 and 0.134 under SMM and RMM, respectively, indicating that genes associated with difficult births also increase intervals between calving and the first insemination afterwards. Comparison of both models by the deviance information criterion (DIC) demonstrated the plausibility of RMMs over SMMs.